[LeetCode 풀이/python] 27. Remove Element (easy)

문제 설명: 하나의 배열 nums 와 하나의 값 val 이 입력으로 주어졌을 때, 주어진 값에 해당하는 모든 원소를 'in-place 방식' 으로 제거하고 남은 새로운 배열의 길이를 구하시오. 이 때, 다른 배열을 위한 추가 공간을 할당할 수 없으며, O(1) 의 추가 메모리를 요구하는 'in-place 방식' 을 통해서만 입력 배열을 수정해야 함. 새로운 배열 내 원소들의 순서는 변경 되어도 무관하며, 새로운 배열 길이를 초과하는 부분에 다른 원소들이 남겨져도 됨.

(cf. in-place 방식: 추가적인 자료 구조를 할당하지 않고, 대체(replace) 또는 교환(swap) 연산을 통해서만 입력 값을 업데이트 하는 것) 

 

(Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.)

 

 

예시 1)

입력: nums = [3,2,2,3], val = 3  --> 출력: 2, nums = [2,2]

설명: 답안으로 작성하는 함수는 새로운 배열 [2,2] 의 길이에 해당하는 숫자인 2 를 출력해야 하며, 동시에 최종 배열 nums 의 첫번째 2개 요소가 새로운 배열 [2,2] 에 해당해야 함. 첫번째 2개 요소만 맞다면, 최종 배열 nums = [2,2,3,3] 또는 nums = [2,2,0,0] 모두 정답이 될 수 있음.

 

예시 2)

입력: nums = [0,1,2,2,3,0,4,2], val = 2  -->  출력: 5, nums = [0,1,4,0,3]

 

제한 조건:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 제거 대상이 되는, 주어진 값 val 에 해당하는 원소는 기존 배열 nums 의 뒤로 몰아주자
  • 1) pointer 는 제거 대상 값 val 에 해당하는 원소를 배열의 후반으로 몰아주기 위해 사용하는 변수로, 배열의 맨 끝 값으로 초기화
  • 2) 기존 배열 nums 의 원소를 앞에서부터 차례로 탐색하며,
    • 해당 원소가 val 에 해당하지 않을 경우, 새로운 배열의 원소가 될 것이므로 새로운 배열의 길이 leng += 1
    • 해당 원소가 val 에 해당할 경우, 해당 원소와 pointer 가 가리키는 원소를 교환(swap) 함
      -- 제거 대상이 되는 원소를 배열의 후반으로 보내고 새로운 배열의 원소가 될 수 있는 값을 앞으로 보냄
      -- 이 때, pointer 가 가리키는 원소가 이미 val 에 해당하는 값일 경우, val 값에 해당하지 않을 때까지 한 칸씩 pointer 를 앞으로 이동시킴
      -- 결과적으로 해당 원소의 인덱스(위치) 에 새로운 배열의 원소가 될 수 있는 값이 오게 되므로 leng += 1
    • pointer 가 기존 탐색 범위를 침범할 경우 (pointer <= i) 이전 단계에서 in-place 방식으로 정렬해온 결과를 어그러뜨리게 되므로 그 전에 탐색을 멈추고 끝냄 (break) 

 

• 코드 구현

def removeElement(self, nums: List[int], val: int) -> int:
    leng = 0
    pointer = len(nums) - 1
    
    for i, n in enumerate(nums):       
        if n != val: leng += 1
        else:
            while (nums[pointer] == val) and (pointer > 0):
                pointer -= 1
            if pointer > i:
                nums[i] = nums[pointer]
                nums[pointer] = val
                leng += 1
            else:
                break
        
    return leng

 

• 결과
  • 선형 시간 복잡도 O(n) 로 무난하게 통과
  • 참고 삼아 Discussion 에서 다른 풀이들을 봤는데 생각보다 훨씬 심플하게 푼 코드들이 있어서 충격 받음

 

 

[풀이 2안]

• 접근법
  • 새로운 배열의 길이에 해당하는 변수 leng 를 인덱스로 사용...!
  • 기존 배열 nums 를 앞에서부터 탐색하면서 각 원소가 val 에 해당하지 않는, 새로운 배열의 원소가 될 수 있는 경우에만 nums[leng] 에 덮어쓰는 방식으로 저장함
  • leng 이 1씩 증가할 수록 이에 맞춰 저장 위치(인덱스) 도 한 칸씩 이동하게 되므로 nums 배열의 앞쪽에 자연스럽게 새로운 배열에 해당하는 원소들로만 구성되게 됨

 

• 코드 구현

def removeElement(self, nums: List[int], val: int) -> int:
    leng = 0
    for n in nums:
    	if n != val:
            nums[leng] = n
            leng += 1
    return leng

 

• 결과
  • 배열 nums 에 대한 선형 탐색이 이루어지므로 시간 복잡도는 풀이 1과 동일하게 O(n)
  • 코드가 간결해서 멋지다... 우왕..