[알고리즘/Python] LeetCode 27. Remove Duplicates from Sorted Array2

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

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,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 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,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
 
Constraints:
1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

---

이 문제는 오름차순으로 정렬된 배열에서 중복된 값을 제외한 결과를 원래의 순서를 유지하여 배열의 앞에서부터 저장하는 문제입니다.

💡접근방법: 값 덮어쓰기

 LeetCode 26. Remove Duplicates from Sorted Array 문제와 모든 요구사항이 동일하지만 이 문제(LeetCode27. Remove Duplicates from Sorted Array2)는 추가 메모리 공간을 사용하지 않고 공간 복잡도 O(1)내에서 해결해야한다는  조건이 추가되어 난이도가 Medium으로 상승되었습니다. 

 

앞에서 풀었던 LeetCode 27.Remove Element 문제와 같이 앞의 k개만 검사 대상이 되므로 뒤에  index k부터 len(nums) - 1까지의 원소의 값은 중복되어도 상관이 없습니다. 따라서 Remove Element에서와 같이 앞에서부터 값을 덮어쓰면서 배열을 순회하는 방법을 떠올릴 수 있습니다.

 

  1. 배열의 첫번째 원소는 항상 가장 작은 원소이면서 맨 앞에 저장되어야하는 원소이므로 두번째 원소부터 값을 덮어쓰도록 index를 1로 초기화합니다. index는 다음으로 유일한 값의 원소가 저장될 인덱스를 의미합니다.

  2. 배열의 두번째 원소부터 순회하면서, 현재 원소와 직전에 덮어쓴 값 nums[index-1]을 비교하여 같다면 중복된 값이라는 것을 알 수 있습니다. 따라서, nums[index] 위치에 값을 덮어쓰고 index를 1증가 시킵니다.

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

 

class Solution(object):
    def removeDuplicates(self, nums):
        index = 1
        for i in range(1, len(nums)):
            if nums[index - 1] != nums[i]:
                nums[index] = nums[i]
                index += 1
        print(nums)
        return index

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 배열을 한번만 순회하고, 값을 덮어쓰는 연산은 배열을 참조하는 연산과 같으므로 총 O(N) 복잡도를 가집니다.

공간 복잡도: O(1). in-place 알고리즘 즉, 주어진 배열 내에서 원소를 재배치하는 알고리즘이므로 추가 공간이 필요없습니다.

---

🤔 다른 사람의 풀이

다음은 LeetCode에서 다른 사람이 제출한 답안 중 추천을 많이 받은 답안입니다.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[j] = nums[i]
                j += 1
        return j

 위에서 작성한 코드와 다른 부분이 있다면 이 코드는 중복된 원소를 판별하기 위해서 바로 이전 원소와 비교한다는 것입니다.

저는 nums[j]와 nums[i]를 비교했다면, 이 코드는 nums[i]와 nums[i-1]를 비교하였습니다. nums[j]의 값은 항상 nums[i-1]의 값과 같으므로 실제로는 같은 코드라고 할 수 있습니다.

 

 하지만, 제출 결과를 보면 제 코드의 경우 실행시간이 71 ms인데 반해 위 코드는 59 ms로 줄어들었습니다. 그 이유는 추측컨데 배열은 메모리에 연속되어 저장되므로 nums[i]와 nums[i-1]는 nums[i]와 nums[j]보다 메모리 상에 물리적으로 가까이 위치하기 때문에 참조하는데 시간이 줄어들어서가 아닐까 생각합니다. 

 

Chat-GPT에 질문해 보았습니다.

 Chat-GPT의 답변을 요약하자면, 메모리를 블럭 단위로 읽어서 캐싱하기 때문에, 지역적으로 가까운 인덱스의 원소일수록 캐싱되어있을 확률이 높으므로 더 빠르게 참조가 가능하다(캐시의 spatial locality)는 것입니다. 

 이 문제의 경우 최대 배열의 길이가 30,000이기 때문에 캐시 지역성 때문에 위와 같은 실행시간의 차이가 발생하였을 수 있습니다.

---

✅ 정리

◎ 시간 복잡도가 같은 알고리즘이라도 실제 실행시간은 차이날  수 있습니다. 인덱스를 참조하는 경우, 가까이 위치한 인덱스를 참조할수록 캐시 공간 지역성의 이점을 살려서 실행시간을 줄일 수 있습니다.