Leetcode - Remove Duplicates from Sorted Array II

16 Oct 2024 in Algorithm

알고리즘 공부

Daily Leetcode

• 🏃‍♂️‍➡️ Naive Solution
• 🎸 Reduce Space Complexity

문제 링크

🏃‍♂️‍➡️ Naive Solution

문제의 조건 중 하나가 추가적인 Space를 쓰지 말고 진행하라고 나와있지만 추가적인 공간을 쓰는 Naive 한 방식의 솔루션은 아래와 같다

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # Naive Solution
        num_cnt = dict()
        wIdx = 0

        for i in range(len(nums)):
            cnt = num_cnt.get(nums[i], 0)
            if cnt < 2:
                nums[wIdx] = nums[i]
                num_cnt[nums[i]] = cnt+1
                wIdx += 1
        
        return wIdx

• Time Complexity : O(n)
• Space Complexity : O(n)

보시다시피 num_cnt 딕셔너리를 이용하여 지금까지 원소가 몇 번 나왔는지를 저장하고 2번 미만으로 나왔다면 그 자리에 원소를 넣어주는 방식으로 진행한다. 추후 나올 솔루션보다 이 방법이 실제 Runtime 속도가 빠르게 나오기는 한다.

🎸 Reduce Space Complexity

이제 면접관이 Space Complexity를 O(1)로 처리해달라고 부탁했을 때, 어떻게 하면 될까?

핵심은 2번 반복됐나를 인덱스를 체크하는 것이다. 현 시점 wIdx-2 인덱스의 원소가 지금과 같다면 그건 2번 반복됐다는 뜻이다.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        wIdx = 2

        for i in range(2, len(nums)):
            if nums[wIdx-2] != nums[i]:
                nums[wIdx] = nums[i]
                wIdx += 1
        return wIdx

코드를 보게된다면 wIdx를 2부터 시작하면서 해당 엘레먼트가 2번 반복됐는지를 체크한다. 이 방법으로 진행할 시 추가적인 공간없이 O(1) 만에 문제를 풀 수 있다.