[Leet Code풀이] 27. Remove Element

문제 설명

https://leetcode.com/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150

val로 주어진 값을 리스트에서 제거한 후, 해당 리스트에 요소가 얼마나 남았는지를 알아내는 알고리즘

풀이

접근 방법 1.

1) val이 nums에 있을때까지 nums를 돌면서 삭제 2) 삭제와 동시에 마지막에 _를 추가한다. 3) 발견과 동시에 cnt를 올리고 이를 원래 길이에서 빼서 리턴

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        org_len = len(nums)
        cnt = 0
        while val in nums:
            nums.remove(val)
            nums.append("_")
            cnt += 1
        return org_len - cnt

위 풀이의 시간 복잡도와 공간복잡도는 아래와 같다.

• 시간 복잡도 : O(N^2) remove 함수의 시간 복잡도가 O(N), 그리고 이를 nums 만큼 반복하므로 O(N^2)

• 공간 복잡도 : O(1) 단순 몇개 변수만 사용하므로 O(1)

위 방식은 시간복잡도가 O(N^2)이므로 인풋이 좀 더 많아지면 꽤나 시간이 오래걸려서 time out이 날 가능성이 크다.

접근 방법 2. Two pointer

Two pointer를 사용하여 두개의 인덱스를 조정해 가면서 중복된 값을 제거해나갔다. 1) left와 right라는 인덱스를 0부터 출발해서 2-1) right가 val인 경우 _로 변환하고 right는 한칸 더 오른쪽으로 간다. 2-2) right가 val이 아닌경우 left와 right를 바꿔주고 둘다 1칸씩 동시에 이동

위 로직을 따르면 3223이라는 인풋에서 3을 지운다고 가정할때 아래와 같은 플로우를 따른다.

3223
_223    <- right가 3이므로 _로 변경 하고 right 은 한칸 오른쪽으로 
2_23    <- left와 right가 다르므로
22_3    <- 둘이 값을 바꿈
22__    <- right가 3이므로 _로 변경

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left, right = 0, 0
        while right < len(nums):
            if nums[right] == val:
                nums[right] = '_'
                right += 1
            else: 
                nums[left], nums[right] = nums[right], nums[left]
                left += 1 
                right += 1
        return left

• 시간 복잡도 : O(N) nums의 크기만큼 시간을 소요한다.

• 공간 복잡도 : O(1) 단순 몇개 변수만 사용하므로 O(1)