[LeetCode] 27. Remove Element

https://leetcode.com/problems/remove-element/

Remove Element - LeetCode

 

array에서 특정 값을 삭제하는데 in-place 방식(extra datastructre를 사용하지 않고 위치를 바꾸는)으로 array를 유지하는 방식.

조건에서 순서는 상관 없다고 하였다.

 

Solution1.

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        cnt = 0
        for num in nums:
            if num != val:
                nums[cnt] = num
                cnt += 1

        return cnt

원하는 조건은 만족하였고 통과.

하지만 뭔가 마음에 들지 않는다.

왜냐?

순서가 상관 없다고 했는데 새로운 값을 assign하는 횟수가 많을 가능성이 크다.

첫 번째 element가 삭제해야하는 숫자라면 최대 n-1 번 array에 새로운 값을 assign 해야한다.

 

최소한의 assign 횟수는 삭제해야 하는 element의 개수와 같다.

 

Solution2.

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        n = len(nums)
        while (i < n):
            if nums[i] == val:
                nums[i] = nums[n-1]
                n -= 1
            else:
                i += 1

        return n

 

이렇게 하면 array에 새로운 값을 assign 횟수가 삭제해야하는 element 개수와 같아진다.