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

#1.  문제

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

Remove Duplicates from Sorted Array - LeetCode

 

 

 

26번 문제와 매우 비슷하다.
정수 리스트 nums에서 중복되는 요소가 있으면 요소 하나만 남기고 제거하여 고유한 요소들로만 채워진 리스트 nums 와 고유한 요소의 갯수 k를 리턴

처음부터 k번째 요소까지 이후의 요소는 어떤 요소가 와도 상관이 없다.

 

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

# output
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

# explanation
중복되는 요소들이 제거된 리스트 nums의 unique한 요소 갯수는 5개이므로 k=5

 

# 참고로 nums 내부적인 요소 변동이 있어야 하므로 함수 내부에 return 값은 존재하지 않는 것이 문제 요구사항

---

#2.  풀이

 

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

 

26번 풀이 방법과 거의 동일하다.
리스트의 고유한 요소들을 "처음부터" 바꾸는 것이 요구사항의 핵심이기 때문에 역시 변경할 요소를 지정하기 위한 인덱스 변수를 change_idx라고 설정하였다.
리스트의 요소를 현재 요소를 바로 이전 요소와 비교하여 값이 다르면 (즉, 중복이 아니라면) 리스트의 처음부터 루프의 현재 요소로 치환하는 과정을 반복한다.
시간복잡도는 O(N)이며 추가적인 메모리 비용은 필요 없다.

IndexError에 유의하여 range와 change_idx만 잘 설정한다면 크게 어려울 것이 없다.

 

---

 

#3.   다른 사람 풀이

 

class Solution:
    # Two Pointer 풀이
    def removeDuplicates(self, nums: List[int]) -> int:
        # standard는 기준 포인터, pointer 는 "중복"되는 숫자를 찾아 앞으로 나갈 포인터
        standard, pointer = 0, 1
        while pointer < len(nums):
            # standard는 숫자와 pointer 숫자가 같으면 중복이므로 pointer 한 칸 더 나감
            if nums[standard] == nums[pointer]:
                pointer += 1

            # standard 숫자와 pointer 숫자가 다르면 standard와 pointer 사이 숫자는 중복된 숫자 (이미 pointer가 본 숫자)
            else:
                # 따라서 현재 standard 요소 바로 옆 요소를 이미 본 숫자로 치환한다.
                # 이로 인해 [0, 0, 1 ...] 이 [0, 1, 1, 1, 2, ...] 이후 [0, 1, 2, 3, ...] 이런식으로 변화한다. (처음 k 번째 unique한 숫자만 있다면 이후 리스트 요소는 아무거나 와도 상관 없음)
                nums[standard + 1] = nums[pointer]
                pointer += 1
                standard += 1

        return standard + 1  # standard는 인덱스이기 때문에 리스트 길이를 구하기 위해서는 1을 더함

 

투 포인터 방식으로 해결한 다른 사람의 풀이를 쉽게 이해할 수 있도록 다시 풀어보았다.
비교 대상인 기준 포인터 standard와 비교하면서 앞으로 나아갈 포인터 pointer를 설정하고,
두 인덱스 요소 값이 같으면 pointer 위치를 다른 값을 찾을때까지 전진시킨다.

다른 값을 찾게 되면 standard 바로 옆 요소를 다른 값으로 치환하는 과정을 거치면서 투 포인터를 한칸씩 옮기는 구조다.
(주석참조)