Leetcode - Remove Duplicate Elements

15 Oct 2024 in Algorithm

알고리즘 공부

Daily Leetcode

• 🥽 Solution
  • 👻 Complexity

문제 링크

중복된 원소를 지우는 문제이다. 이건 사실 Naive를 생각하는게 더 어려운 문제이다. 굳이 생각하자면 count() 함수를 써서 이렇게 저렇게 해보겠다~ 라고 하지만 결국 핵심 in-place 에서 삭제가 이뤄져야 한다. 그럼 결국 포인터를 쓸 수 밖에..

🥽 Solution

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        """
        오름차순 정렬이 되어 있다는 것 -> 중복이 되어있다면 연속해서 등장한다는 것
        """

        idx = 0
        n = len(nums)

        for i in range(n):
            if nums[i] != nums[idx]: #중복되지 않은 숫자 발견
                idx += 1
                nums[idx] = nums[i]

        return idx+1

주석에도 써놓았지만 이 문제의 힌트는 오름차순 정렬이 되어 있다는 것이다. 그렇다면 중복이 있는 경우라면 어쩔 수 없이 연속해서 등장할 수 밖에 없다는 것이다.

그래서 코드를 보면 idx를 잡아놓고 이전의 nums[idx] 와 다르다면 새로운 원소가 나왔다는 뜻이므로 idx를 하나 올려주고 그 idx 자리에 해당 데이터로 바꿔주는 것이다.

이렇게 되면 결국 idx는 마지막에 중복된 것까지의 원소를 가르키고 있기에 +1을 해주어 중복되지 않은 숫자가 몇개인지를 알려줄 수 있게 된다.

👻 Complexity

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