LeetCode 80(Remove Duplicates from Sorted Array II)

1. 문제 링크

• https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

Remove Duplicates from Sorted Array II - LeetCode

2. 문제 설명

• 오름차순으로 정렬된 nums라는 array가 있을 때, 각 element가 최대 2번씩만 등장하도록 일부 duplicates를 제거하는 문제 
• 만약 duplicates를 제외하고 k개의 element가 있다면, 이를 nums의 첫 k공간에 넣고, 그 이후에 대해서는 어떤 걸 남겨도 상관없음 
• 제약 조건
  • in-place 방식으로 코드를 작성해야 할 것
  • 다른 array에 추가 공간을 할당하는 구조로 하면 안되며, 반드시 O(1) exrtra memory만 사용해서 array를 수정할 것 
• 예시1) nums = [1,1,1,2,2,3]이면 output = [1,1,2,2,3,_] 마지막 _는 어떤게 와도 상관 없음
• 예시2) nums = [0,0,1,1,1,1,2,3,3] 이면 output = [0,0,1,1,2,3,3,_,_]

3. 처음 풀이

• 이게 출제자의 의도는 아닐 것 같았으나, 가장 간단히 해결 할 수 있는 방법 같아서 아래처럼 코드 작성.
• cur_num에는 현재의 element값을 저장하고 (초기값은 nums[0]으로 셋팅)
• cnt 는 cur_num이 몇번 등장했는지를 체크하기 위해 셋팅.
  • nums[:]에 대해 for문을 돌리면서, 만약 i가 cur_num과 같으면 cnt를 한개씩 올리고,
  • 같지 않다면 cur_num을 현재의 i로 업데이트, cnt는 1로 다시 reset을 하였다.
  • 그리고 만약 cnt 가 2보다 크다면, nums에서 그 값을 remove 하고, cnt는 -1 해주는 구조로 작성
• 이렇게 하면 공간 복잡도가 O(1)로 조건을 부합하긴 하나, 난이도가 medium인데 이게 의도가 맞는건가 하는 생각이 들었음. 
  • 내 풀이의 경우 for문을 돌리고, 그 안에서 nums.remove(i)까지 수행하기 때문에, 최악의 케이스에서는 시간 복잡도가 O(n^2)이 된다. 
  • 공간복잡도는 출제에서 의도한 대로 O(1)이 맞으나, 어쨌든 코드의 개선이 필요.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        cur_num = nums[0]
        cnt = 0
        
        for i in nums[:]:
            if i == cur_num:
                cnt += 1
            else:
                cur_num = i
                cnt = 1
            if cnt > 2:
                nums.remove(i)
                cnt -=1

 

4. 다른 풀이

• list.pop이나 list.remove를 하지 않고, 정렬하려면 어떻게 해야 할까?
• [1,1,1,2,2,2,3] 이 있다고 하면
  • [1,1,2,2,2,2,3] → [1,1,2,2,2,3,3] → [1,1,2,2,3,3,3] 이렇게 
  • 2번 이상 등장한 element의 가장 마지막 위치에 있는 것을 그 다음 element로 바꿔주는 것을 반복하다보면, 
  • 1,1,2,2,3,3으로 정렬이 가능하다. 
• 이를 코드로 표현해보면
  • 우선 nums길이가 2보다 작거나 같다면 정렬할 필요가 없으므로, 따로 빼주고, 
  • index의 초기값을 2로 셋팅한다음, nums를 iteration돌면서
    • nums[i]와 nums[index-2]가 동일하다면, 그 시점의 index는 다음 element값으로 바꿔주는 것이 필요하다.
    • 따라서, 동일한 경우는 index를 변화시키면 안되기 때문에, pass를 하고, 
    • nums[i]와 nums[index-2]값이 다르게 되면, 
      • nums[index]에 nums[i]를 할당하고, index는 그 다음 커서로 이동해주는 걸 반복하게 된다.
• 이렇게 코드를 작성하면, 공간복잡도는 기존풀이인 O(1)과 동일하지만, 시간복잡도가 O(N)으로 개선이 된다.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return len(nums)

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

        return index

5. 배운 점 

• 시간 복잡도 개선하기