[Python] LeetCode 80. Remove Duplicates from Sorted Array II

문제 풀이

리스트 원소의 중복된 값을 2개까지만 허용하고, 나머지는 제거하는 문제이다.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        cnt_arr = [0] * (max(nums) + 1)
        cnt = 0
        for i in range(len(nums)):
            cnt_arr[nums[cnt]] += 1
            if cnt_arr[nums[cnt]] == 3:
                cnt_arr[nums[cnt]] -= 1
                del nums[cnt]
                cnt -=1
            cnt += 1

처음에는 위와 같이 리스트를 만들어 값을 해당 값이 몇 개인지 기록을 했었는데 음수 값도 존재하기 때문에 음수를 표현하기 곤란해서 리스트 대신 딕셔너리를 활용했다.

1. int defaultdict를 선언해준다.

2. for문으로 리스트를 탐색한다.

3. 딕셔너리에 해당 값의 개수를 1씩 더해준다.

4. 해당 값의 개수가 3개가 되는지 확인한다.

5. 해당 값의 개수가 개가 되면 해당 인덱스의 원소를 제거해준다.

6. 이 과정을 반복한다.

※ 주의해야 될 점은 중복 개수가 3개가 되어서 제거했을 때, 기록한 중복 값을 1 빼주고, 제거 된 원소의 빈자리를 뒷부분 원소들이 당겨져서 채워지기 때문에 다시 현재 인덱스를 탐색해야 한다.

답

from collections import defaultdict
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        nums_cnt = defaultdict(int) ## 1. int defaultdict를 선언해준다.
        cnt = 0
        for i in range(len(nums)): ## 2. for문으로 리스트를 탐색한다.
            nums_cnt[nums[cnt]] += 1 ## 3. 딕셔너리에 해당 값의 개수를 1씩 더해준다.
            if nums_cnt[nums[cnt]] == 3: ## 4. 해당 값의 개수가 3개가 되는지 확인한다.
                nums_cnt[nums[cnt]] -= 1
                del nums[cnt] ## 5. 해당 값의 개수가 개가 되면 해당 인덱스의 원소를 제거해준다.
                cnt -=1
            cnt += 1