[알고리즘/Python] LeetCode 80. Remove Duplicates from Sorted Array 2

문제

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

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

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).

Constraints:
1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in non-decreasing order.

---

이전에 풀어본 LeetCode 26. Remove Duplicates from Sorted Array 문제와 달리 난이도가 Medium으로 더 어렵습니다. 그 이유는 중복된 원소를 두번까지는 저장해야하기 위해 각 원소가 등장한 횟수를 기억해야하기 때문입니다.

💡 접근방법

  1. pos는 다음으로 원소가 저장될 인덱스를 의미하며 1로 초기화합니다. 배열의 첫번째 원소는 항상 가장 작은 원소이면서 맨 앞에 저장되어야하는 원소이므로 두번째 원소부터 값을 덮어쓰게 됩니다. count는 마지막으로 저장된 값의 등장 횟수입니다. nums[0]원소가 1번 등장했으므로 1로 초기화합니다.

  2. 배열의 두번째 원소부터 순회하면서, 현재 원소와 이전 원소를 비교합니다.

      - 만약 이전 원소와 값이 다르다면 중복되지 않은 새로운 값이 등장한 것이므로, 값을 nums[pos]에 덮어쓴 후 pos를 1 증가시키고, count에는 1을 대입합니다.

     - 이전 원소와 값이 같다면, count 값에 따라 처리합니니다. count가 1이라면 (이전에 한번이라도 등장했으므로 count는 0이 될 수 없음) 한번 더 저장할 수 있으므로 값을 덮어쓰고, pos와 count를 증가시킵니다. count가 2이상이라면 더 이상 저장할 수 없으므로 값은 덮어쓰지 않고, count만 증가시킵니다.

  3. index를 반환합니다. 배열의 0부터 index-1 까지의 원소 즉 앞에서부터 index개의 원소는 기존의 배열에서 3번이상 중복된 값을 제거한 결과입니다.

 

class Solution(object):
    def removeDuplicates(self, nums):
        pos = 1
        count = 1
        for i in range(1, len(nums)):
            if nums[i - 1] != nums[i]:
                nums[pos] = nums[i]
                pos += 1
                count = 1
            else:
                if count < 2:
                    nums[pos] = nums[i]
                    pos += 1
                count += 1

        return pos

 만약 배열의 길이가 1이라면 for문을 돌지 않고 그대로 pos를 반환합니다.

✔️시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 배열을 한번만 순회하고, 각 for문 안에서 값을 비교하고 값을 덮어쓰는 연산은 배열을 참조하는 연산과 같이 O(1) 시간이 소요되므로 총 O(N) 시간 복잡도를 가집니다.

공간 복잡도: O(1). 별도의 배열을 선언하지 않고 배열을 in-place에서 조작해야하는 문제의 제약사항 상 O(1) 공간 복잡도를 가집니다.

---

🤔 다른 사람의 풀이: Counter 라이브러리 사용

 Counter 라이브러리를  사용하여 원소별 개수를 센 후 원소의 개수에 따라서 nums배열에 덮어씁니다.

 

이때 Counter에 의해서 생성된 dictionary는 unordered collection으로 삽입된 순서를 유지하지는 않지만, key 값에 따라 오름차순 정렬되기 때문에 dictionary의 item순서와 nums 배열의 원소들의 순서는 일치합니다. 따라서, dictionary의 item을 순회하면서 nums배열에 값을 덮어쓴다면 상대적인 순서를 유지해야한다는 문제의 조건을 지킬 수 있습니다. 

 

이 방법은 시간 복잡도는 저의 풀이와 다르지 않지만 공간 복잡도가 더 큰 방법입니다.  시간 복잡도는 O(N)입니다. 원소별 개수를 세는데 O(N) 시간이 소요되고, 세어진 결과를 iterate하면서 배열에 덮어쓰는데 최대 O(N) 시간이 소요됩니다. 따라서 시간 복잡도는 저의 풀이와 다르지 않습니다. 다만, 배열을 한번 순회하고 나서도, counter 딕셔너리를 한번 더 순회해야하므로 실제 연산 횟수는 더 많을것입니다.

 공간 복잡도는 배열을 따로 선언하지는 않지만 새로 만든 딕셔너리를 위한 공간이 필요합니다. 모든 원소가 중복되지 않을 경우 Counter 딕셔너리에 총 N개의 item이 생기게 됩니다. 따라서 공간 복잡도는 O(N)으로 저의 풀이의 O(1) 보다 더 큰 공간을 필요로 합니다.

from collections import Counter

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        counter = Counter(nums)
        index = 0

        for num, count in counter.items():
            nums[index] = num
            index += 1
            if count > 1:
                nums[index] = num
                index += 1

 다만, 문제에서 새로운 배열에 공간을 할당하지 말라고 하였지만, 실제로 다른 사람들의 풀이를 보거나, 위의 풀이에서도 별도의 공간을 할당하는 것으로 보아서 LeetCode에서 별도의 공간을 사용하는 경우 채점시 fail이 발생하도록 하지는 않는 것 같습니다.

---

✅ 정리

◎ count변수를 사용하여 원소가 등장한 횟수를 세거나, Counter 라이브러리를 사용하여 원소별 등장한 횟수를 dictionary형태로 셀 수 있습니다. 다만 Counter 원소는 순서가 없는(삽입된 순서를 유지하지 않는) unordered collection이라는 것을 주의해야합니다.