[PS] LeetCode: Remove Duplicates from Sorted Array

오늘은 LeetCode의 Remove Duplicates from Sorted Array 문제를 풀어보겠습니다.

 

문제

정렬된 `nums`라는 정수 배열이 주어졌습니다. 추가 메모리를 사용하지 않고(in-place), 배열을 직접 수정해서 중복된 값을 제거해야 합니다. 최종적으로 고유한 원소의 개수 `k`를 반환하세요.

 

예제

Input: nums = [1, 1, 2]
Output: 2, nums = [1, 2, _]

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

 

접근 방법

이 문제의 핵심은 배열이 "정렬되어 있다"는 점입니다. 이 상황에서 같은 값들은 항상 서로 인접해 있기 때문에 이전 원소와만 비교해도 중복을 감지할 수 있습니다. 이 아이디어를 깔끔하게 구현하기 위한 대표적인 패턴이 투 포인터입니다.

• l: 고유한 구간의 마지막 인덱스
• r: 새로 탐색 중인 인덱스 

예를 들어, nums = [0, 0, 1, 1, 2]라고 해보겠습니다.

단계	l	nums[l]	nums[r]	동작
r = 0	0	0	0	-
r = 1	0	0	0	중복이라 건너뜀
r = 2	0	0	1	두 값이 다르므로, l += 1, nums[1] = 1
r = 3	1	1	1	중복이라 건너뜀
r = 4	1	1	2	두 값이 다르므로, l += 1, nums[2] = 2

 

최종적으로 nums는 [0, 1, 2, 1, 2]가 되고, 앞의 3개(l + 1)가 고유한 구간입니다. 이를 파이썬으로 구현해보겠습니다. 

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 0

        for r in range(len(nums)):
            if nums[l] != nums[r]:
                l += 1
                nums[l] = nums[r]

        return l + 1

 

복잡도 분석

• 시간 복잡도: O(n)

이 알고리즘은 입력 배열을 한번만 순회합니다. r 포인터는 왼쪽에서 오른쪽으로 배열 전체를 훑고, l 포인터는 새로운 원소를 발견할 때만 이동합니다. 두 포인터가 함께 움직이더라도, 실제 비교 연산의 총 횟수는 배열의 길이 n을 넘지 않기 때문에 전체 시간 복잡도는 O(n)입니다.

• 공간 복잡도: O(1)

이 알고리즘은 입력 배열을 in-place 방식으로 수정합니다. 입력 크기 n이 커지더라도 추가로 사용하는 변수는 l과 r 두 개로, 입력 크기에 관계없이 메모리 사용량이 일정하므로 공간 복잡도는 O(1)입니다.

 

나가며

투 포인터 패턴의 기본 문제였습니다. 다음에는 이 아이디어를 확장한 다른 문제들을 풀어보겠습니다.