[리트코드] 80. Remove Duplicates from Sorted Array II

문제

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/?envType=study-plan-v2&envId=top-interview-150

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

 

---

✔ 문제접근 #1 선형탐색[통과] ⭕

Intuition

주어진 배열은 오름차순 정렬되어있다.

같은 숫자가 연속해서 나올 것이므로 현재 자신의 위치에서 2칸 뒤의 값이 자신과 같다면 최소 3개이상 연속해있다는 의미이다. 이것을 이용하여 선형탐색으로 문제를 해결한다.

Algorithm

값을 집어넣을 위치를 나타내는 idx를 선언한다.nums 배열의 값을 하나씩 순회하면서 자신 뒤의 2번째 값이 같지 않으면 idx위치에 자신의 값을 넣어준다.만약 요소의 뒤에 2번째 값이 배열 범위의 초과로 탐색할 수 없다면 그냥 비교하지 않고 그냥 idx 위치에 넣어준다.

    def removeDuplicates(self, nums: List[int]) -> int:
        
        idx = 0
        for i in range(len(nums)):
            if i > len(nums) - 3:
                nums[idx] = nums[i]
                idx += 1
                continue
                
            if nums[i] != nums[i + 2]:
                nums[idx] = nums[i]
                idx += 1
        
        return idx

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • num 배열을 순차탐색 O(N)
  • 그러므로 전체시작복잡도 : O(N)

• 공간복잡도 : O(1)
  
  • 기존의 num 배열을 재사용하기 때문에 추가적인 메모리를 사용하지 않는다.

---

기타풀이 및 회고

nums[i] != nums[i + 2] 부분에서 index error 를 조심해야한다.

index error 발생의 여지가 있는 부분은 항상 먼저 if 문으로 조건을 걸어줘야함에 주의하자.