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

주어진 조건

• 정수 배열 nums
• 각 고유 요소가 최대 두 번만 나타나도록 중복된 요소를 nums에서 제거하자

문제

• nums가 아닌 nums의 요소 수 k를 return
• nums 배열에서 k번째까지의 요소만 관심이 있고, 그 이후의 요소에는 뭐가 들어있든지 상관 없다

---

나의 풀이

Remove Duplicates from Sorted Array 1 에서 배웠던 풀이인 Two Pointers 를 사용해 풀었다.

• 최대 2번의 중복을 허용하기 때문에 slow 포인터가 가리키는 요소와, 그 전의 요소 이 두 값과 fast 포인터가 가리키는 요소를 비교
• 만약 두 값과 모두 같다면, 더 이상의 중복이 허용되지 않으므로 fast 포인터의 값을 증가시킨다.
• 아니라면 slow 포인터 + 1 위치에 fast 포인터가 가리키던 값을 넣고, slow, fast 포인터 두 값다 1씩 증가

구현 코드

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow, fast = 1, 2
        while fast in range(len(nums)):
            if nums[slow-1] == nums[fast] and nums[slow] == nums[fast]:
                fast += 1
            else:
                nums[slow+1] = nums[fast]
                slow += 1
                fast += 1
        
        return slow + 1

---

다른 풀이

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for n in nums:
            if i < 2 or n > nums[i-2]:
                nums[i] = n
                i += 1
        return i

앞서 봤던 나의 풀이에서 새로 배운 Two Pointer 를 바로 적용해 풀이해서 제일 좋은 코드라 생각했지만 아니었다.

내 풀이의 문제점

• while 루프 안에 ‘in’ 연산자의 속도 저하 가능성
• 두 개의 포인터 변수 관리

위의 코드 처럼 배열이 정렬되어 있는 상태 라는 것을 이용하면 좀 더 빠른 코드를 구현할 수 있다.

이미 정렬되어 있으므로, nums[i-2] 보다 n이 더 크다면, 아직 중복 허용 2번을 넘지 않았다는 것이다.

ex)

nums = [1, 2, 2, 3, 3, 3, 4]

i = 2

n = 2

일 경우, n > nums[0] ⇒ true

nums[i]에 n 값을 넣고, i를 증가시킨다.