[Leetcode] 80. Remove Duplicates from Sorted Array II (python)

#1.  문제

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

Remove Duplicates from Sorted Array II - LeetCode

 

 

 

27번 문제의 변형 기출이라고 볼 수 있다.

기존의 중복되는 요소를 남기고 고유한 요소만 남기는 방식에서 중복 요소를 2개까지 남기는 형태로 난이도가 조금 올라 갔다.

 

# input
nums = [0,0,1,1,1,1,2,3,3]

# output
7, nums = [0,0,1,1,2,3,3,_,_]

# explanation
중복되는 요소를 2개까지만 허용하여 남기기 때문에 k=7

 

---

#2.  풀이

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        import collections

        nums_map = collections.defaultdict(int)

        for num in nums:
            nums_map[num] += 1

        # 변경할 인덱스 설정
        change_idx = 0

        for key, value in nums_map.items():
            if value >= 2:  
                nums[change_idx : change_idx + 2] = [key] * 2
                change_idx += 2  # 기준 인덱스 변경
            else:
                # 중복 요소가 없는 경우 요소 1개만 변경한다.
                nums[change_idx : change_idx + 1] = [key] * 1
                change_idx += 1  # 기준 인덱스 변경

        return change_idx

 

투포인터로 풀이하다가 계속해서 마지막 인덱스 요소를 처리하는 과정에서 실패했다.
예외 처리가 원인인지 혹은 알고리즘 자체에 문제가 있는 건지 해결에 꽤나 시간을 들였지만 그럴듯한 방법을 도출하지 못했다.

다른 방법을 고민하다가 nums 요소의 중복 수를 해시맵으로 표현하고 중복이 2개 이상인 요소들은 최대 2개까지만 리스트 요소를 변경하도록 알고리즘을 짰다.

 

여기서도 역시 변경할 인덱스를 설정하는 용도로 change_idx 변수를 설정하였다.

 

요소 갯수를 세는 용도로 Counter 모듈을 쓰면 코드가 조금 깔끔해지지만,  개인적으로 딕셔너리를 사용하는 것이 틀린 지점을 트래킹하는데 더 편하다고 생각한다.

 

KeyError를 방지하기 위해 defaultdict 모듈을 사용하고 value값이 2개 이상인 요소는 change_idx 부터 2개까지, 중복이 없는 요소는 1개까지 루프의 현재 key 값으로 변경한다.

 
시간 복잡도는 O(n)이며 별도의 추가적인 메모리 비용이 들지 않는다.