Remove Duplicates from Sorted Array — 정렬 배열을 고유 값 구간으로 압축하기

정렬 배열에서 중복을 제거하기, 어떤 문제인가요?

LeetCode 26번 문제는 이렇게 주어집니다.

오름차순이 유지되는 정수 배열 nums가 주어집니다. 중복된 값을 제자리(in-place) 에서 제거해서 각 값이 한 번만 나오게 만들고, 고유 원소 개수 k를 반환하세요.

정답으로 인정되려면:

• nums의 앞쪽 k개에 고유한 값들이 정렬된 순서로 들어 있어야 하고
• 그 뒤쪽 값들은 무엇이든 상관없습니다

예시는 이렇습니다.

• nums = [1,1,2] → k = 2, nums[:2] = [1,2]
• nums = [0,0,1,1,1,2,2,3,3,4] → k = 5, nums[:5] = [0,1,2,3,4]

제약은 다음과 같습니다.

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100
• nums는 감소하지 않는 순서로 정렬되어 있음

이 문제의 핵심은 배열 전체를 깨끗하게 바꾸는 것이 아닙니다. 앞쪽 k칸만 고유 값들로 채우고, k를 반환하면 됩니다. 이 글에서는 별도 리스트를 쓰는 직관적인 풀이부터, 쓰기 포인터로 제자리에서 고유 값 구간을 만드는 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

정렬되어 있다는 조건 활용하기

배열이 정렬되어 있으므로 같은 값은 항상 붙어 있습니다.

[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

이 배열에서 고유 값의 시작 지점만 보면 됩니다.

0, 1, 2, 3, 4

즉 새 값이 등장하는 순간만 앞쪽에 써 주면 됩니다. 이 관점으로 보면 문제는 다음처럼 바뀝니다.

중복 그룹에서 첫 번째 값만 남기고
그 값들을 nums 앞쪽에 순서대로 압축하라

Phase 1. 새 리스트에 고유 값만 모으기

가장 먼저 떠올릴 수 있는 방법은 고유 값만 새 리스트에 모은 뒤, 다시 nums 앞쪽에 복사하는 것입니다.

fun removeDuplicates(nums: IntArray): Int {
    val unique = mutableListOf<Int>()

    for (num in nums) {
        if (unique.isEmpty() || unique.last() != num) {
            unique.add(num)
        }
    }

    for (i in unique.indices) {
        nums[i] = unique[i]
    }

    return unique.size
}

nums = [1,1,2]라면:

• 1을 추가
• 다음 1은 이미 마지막 고유 값과 같으므로 건너뜀
• 2를 추가
• 앞쪽에 [1,2]를 복사하고 2 반환

정답은 맞습니다. 하지만 unique 리스트를 따로 만들기 때문에 추가 공간이 O(n)입니다. 문제는 제자리 수정을 요구하므로, 다음 단계에서는 이 리스트 역할을 nums 앞쪽 구간이 직접 맡게 만듭니다.

Phase 2. 쓰기 포인터로 고유 값 구간 만들기

별도 리스트 없이 풀려면 nums의 앞쪽을 "고유 값이 쌓이는 구간"으로 사용하면 됩니다.

fun removeDuplicates(nums: IntArray): Int {
    var write = 1

    for (read in 1 until nums.size) {
        if (nums[read] != nums[write - 1]) {
            nums[write] = nums[read]
            write++
        }
    }

    return write
}

여기서 의미는 이렇습니다.

• read: 배열을 왼쪽에서 오른쪽으로 읽는 위치
• write: 다음 고유 값을 써야 할 위치
• nums[write - 1]: 지금까지 앞쪽에 쓴 마지막 고유 값

첫 번째 원소는 항상 고유 값입니다. 그래서 write = 1에서 시작합니다.

nums = [0,0,1,1,1,2,2,3,3,4]를 따라가 봅시다.

처음: nums[0] = 0은 이미 고유 값, write = 1

read=1 -> nums[1]=0, 마지막 고유 값 0과 같음 -> 건너뜀
read=2 -> nums[2]=1, 마지막 고유 값 0과 다름 -> nums[1]=1, write=2
read=3 -> nums[3]=1, 마지막 고유 값 1과 같음 -> 건너뜀
read=4 -> nums[4]=1, 마지막 고유 값 1과 같음 -> 건너뜀
read=5 -> nums[5]=2, 마지막 고유 값 1과 다름 -> nums[2]=2, write=3
read=6 -> nums[6]=2, 마지막 고유 값 2와 같음 -> 건너뜀
read=7 -> nums[7]=3, 마지막 고유 값 2와 다름 -> nums[3]=3, write=4
read=8 -> nums[8]=3, 마지막 고유 값 3과 같음 -> 건너뜀
read=9 -> nums[9]=4, 마지막 고유 값 3과 다름 -> nums[4]=4, write=5

최종적으로 중요한 앞쪽 구간은 이렇게 됩니다.

nums[:5] = [0, 1, 2, 3, 4]
k = 5

시간 복잡도는 O(n)이고, 추가 공간은 O(1)입니다.

왜 nums[write - 1]와 비교하나요?

nums[write - 1]는 지금까지 확정한 마지막 고유 값입니다.

반복문이 진행되는 동안 항상 다음 상태를 유지합니다.

nums[0 .. write-1]에는 지금까지 발견한 고유 값들이
정렬된 순서 그대로 들어 있다

현재 값 nums[read]가 마지막 고유 값과 같으면 이미 앞쪽에 들어 있는 값입니다. 그래서 건너뜁니다.

현재 값이 마지막 고유 값과 다르면 새로운 값입니다. 이때 nums[write]에 쓰고 write++ 하면 앞쪽 고유 값 구간이 한 칸 늘어납니다.

배열이 정렬되어 있기 때문에 이 비교만으로 중복 여부를 판단할 수 있습니다.

Remove Element와 어떤 차이가 있나요?

Remove Element는 특정 값 val만 제거하면 되는 문제였습니다. 그래서 val이 아닌 값만 앞쪽에 모으면 됐고, 순서도 필수 조건은 아니었습니다.

이 문제는 다릅니다.

• 제거 대상이 특정 값 하나가 아니라 중복 전체
• 앞쪽 k개는 고유 값
• 상대 순서가 유지되어야 함
• 입력 배열이 정렬되어 있어서 중복 그룹을 쉽게 찾을 수 있음

따라서 핵심 비교 대상은 val이 아니라, 마지막으로 앞쪽에 쓴 고유 값입니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
[1]	1, [1]	원소 하나는 항상 고유
[1,1,1]	1, [1]	모두 같은 값
[1,2,3]	3, [1,2,3]	중복 없음
[-3,-3,-1,0,0,2]	4, [-3,-1,0,2]	음수도 같은 방식
[0,0,1,1,1,2,2,3,3,4]	5, [0,1,2,3,4]	여러 중복 그룹

이 문제는 제약상 빈 배열이 들어오지 않습니다. 그래서 최종 풀이에서 write = 1로 시작해도 안전합니다. 만약 빈 배열까지 처리해야 하는 일반 함수라면 처음에 if (nums.isEmpty()) return 0을 추가하면 됩니다.

두 풀이를 다시 비교

풀이	시간	공간	특징
새 리스트에 고유 값 저장	O(n)	O(n)	이해하기 쉽지만 제자리 조건에 맞지 않음
쓰기 포인터로 앞쪽 압축	O(n)	O(1)	문제 요구를 그대로 만족하는 기본 풀이

마무리

1. 이 문제는 중복을 실제로 삭제하는 문제가 아니라 앞쪽 k칸을 고유 값으로 채우는 문제입니다 — 뒤쪽 값은 무시됩니다
2. 배열이 정렬되어 있어서 같은 값은 항상 붙어 있습니다 — 마지막 고유 값과만 비교해도 충분합니다
3. write는 다음 고유 값을 쓸 위치입니다 — nums[0 .. write-1]가 항상 정답 후보 구간입니다
4. 첫 번째 원소는 항상 고유 값이므로 write = 1에서 시작합니다 — 입력 길이가 1 이상이라는 제약 덕분입니다
5. 최종 풀이는 O(n) 시간, O(1) 공간입니다 — 한 번 순회하면서 제자리에서 해결합니다