Python으로 정렬된 배열에서 중복 제거하기 (O(1) 추가 공간)

정렬된 리스트 A가 주어졌을 때, 모든 중복 항목을 제거한 뒤 배열의 길이를 반환해야 합니다. 이 문제에는 추가 공간을 O(1)만 사용할 수 있다는 제약 조건이 있으므로, 연산은 반드시 제자리(in-place) 방식으로 수행해야 합니다.

예를 들어 A = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]라면, 고유한 원소는 1, 2, 3, 4, 5, 6으로 총 6개이므로 출력 결과는 6이 됩니다.

해결 알고리즘

배열이 이미 정렬되어 있다는 점이 핵심 힌트입니다. 정렬된 상태에서는 중복된 값들이 항상 서로 인접해 있기 때문에, 배열을 한 번만 순회하면서 현재 원소와 바로 앞 원소(prev)를 비교하는 방식으로 중복 여부를 판별할 수 있습니다. 이러한 기법은 일반적으로 두 포인터(Two Pointer) 방식이라고 불립니다.

구체적인 해결 단계는 다음과 같습니다.

1. 리스트가 비어 있으면 0을 반환합니다.
2. prev를 A의 첫 번째 원소로 초기화하고, length를 1로 설정합니다.
3. i를 1부터 n-1까지 순회하면서, A[i]가 prev와 같지 않다면 length를 1 증가시키고 prev 값을 A[i]로 갱신합니다.
4. 모든 순회가 끝나면 length를 반환합니다.

그럼 실제 구현 코드를 통해 더 자세히 살펴보겠습니다.

파이썬 구현 예제

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        length = 1
        previous = nums[0]
        index = 1
        for i in range(1, len(nums)):
            if nums[i] != previous:
                length += 1
                previous = nums[i]
                nums[index] = nums[i]
                index += 1
        return length

input_list = [1,1,2,2,2,3,3,3,3,4,5,5,5,6]
ob1 = Solution()
print(ob1.removeDuplicates(input_list))

입력

[1,1,2,2,2,3,3,3,3,4,5,5,5,6]

출력

6

복잡도 분석

시간 복잡도: O(n) — 배열 전체를 한 번만 순회하므로 입력 크기에 비례합니다.
공간 복잡도: O(1) — 몇 개의 변수(length, previous, index)만 사용하며, 추가적인 자료구조 없이 배열 내부에서 직접 처리합니다.

이처럼 정렬된 배열의 특성을 활용하면 별도의 집합(set)이나 딕셔너리 없이도 효율적으로 중복을 제거할 수 있습니다. 이 알고리즘은 코딩 테스트 및 LeetCode의 "Remove Duplicates from Sorted Array" 문제에 그대로 적용할 수 있는 대표적인 풀이 방식입니다.