Duplicate Zeros — 고정 길이 배열을 오른쪽에서부터 제자리 갱신하기

0을 복제하면서 배열 길이는 그대로 유지하기, 어떤 문제인가요?

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

고정 길이 정수 배열 arr가 주어집니다. 각 0을 복제하고, 나머지 원소들을 오른쪽으로 밀어내세요. 원래 배열 길이를 넘어가는 값은 버립니다. 배열을 제자리(in-place) 에서 수정해야 하며, 아무것도 반환하지 않습니다.

예시는 이렇습니다.

• arr = [1, 0, 2, 3, 0, 4, 5, 0] → [1, 0, 0, 2, 3, 0, 0, 4]
• arr = [1, 2, 3] → [1, 2, 3]

제약은 다음과 같습니다.

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

이 문제의 핵심은 0을 두 번 써야 하지만, 배열 길이는 늘어나지 않는다는 점입니다. 즉 뒤로 밀려난 값 중 일부는 잘려 나갑니다. 이 글에서는 별도 배열을 쓰는 직관적인 풀이부터, 오른쪽에서부터 덮어쓰는 제자리 O(n)/O(1) 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

왜 Move Zeroes와는 다른 문제인가요?

Move Zeroes는 0을 뒤로 보내고, 0이 아닌 값의 상대 순서를 유지하는 문제였습니다. 그 문제는 결국 0이 아닌 값들을 앞으로 압축하면 됩니다.

하지만 이 문제는 정반대입니다.

• 0을 없애는 것이 아니라 복제해야 함
• 배열 길이가 고정이라 뒤쪽 값 일부는 버려짐

예를 들어:

[1, 0, 2, 3]

에서 0을 복제하면 논리적으로는:

[1, 0, 0, 2, 3]

가 되어야 하지만, 배열 길이는 4이므로 실제 결과는:

[1, 0, 0, 2]

입니다.

즉 이 문제는 "길이가 늘어난 가상의 결과를 생각하되, 실제 배열에는 앞의 n칸만 남긴다"로 보면 이해가 쉽습니다.

Phase 1. 별도 배열에 결과를 만들어 복사하기

가장 직관적인 방법은 새 배열을 하나 만들고, 원본을 읽으면서 결과를 써 나가는 것입니다.

fun duplicateZeros(arr: IntArray) {
    val result = IntArray(arr.size)
    var write = 0

    for (num in arr) {
        if (write >= arr.size) break

        result[write++] = num
        if (num == 0 && write < arr.size) {
            result[write++] = 0
        }
    }

    for (i in arr.indices) {
        arr[i] = result[i]
    }
}

arr = [1, 0, 2, 3, 0, 4, 5, 0]를 따라가면:

• 1 기록 → [1, _, _, _, _, _, _, _]
• 0 기록 + 한 번 더 기록 → [1, 0, 0, _, _, _, _, _]
• 2, 3 기록 → [1, 0, 0, 2, 3, _, _, _]
• 다음 0 기록 + 한 번 더 기록 → [1, 0, 0, 2, 3, 0, 0, _]
• 4 기록 → [1, 0, 0, 2, 3, 0, 0, 4]
• 그 뒤 값은 길이를 넘으므로 무시

정답은 맞지만, result 배열 때문에 O(n) 추가 공간이 듭니다. 문제는 제자리 수정을 요구하므로 여기서 한 단계 더 가야 합니다.

Phase 2. 오른쪽에서부터 덮어쓰기

제자리로 하려면 앞에서부터 쓰면 안 됩니다. 0을 복제하는 순간 아직 읽지 않은 값을 덮어써 버리기 때문입니다.

대신:

1. 최종적으로 각 원소가 가상의 몇 번째 위치로 가는지 생각하고
2. 실제 쓰기는 오른쪽에서부터

하면 아직 읽지 않은 값을 망가뜨리지 않을 수 있습니다.

핵심 아이디어는 이렇습니다.

• zeros = arr 안의 0 개수
• 가상의 최종 길이 = arr.size + zeros
• 실제 배열은 그중 앞의 arr.size칸만 남김

그래서:

• 읽기 포인터 read는 원본 배열의 끝에서 시작
• 쓰기 포인터 write는 가상 배열의 끝에서 시작

합니다.

fun duplicateZeros(arr: IntArray) {
    var zeros = 0
    for (num in arr) {
        if (num == 0) zeros++
    }

    var read = arr.lastIndex
    var write = arr.lastIndex + zeros

    while (read >= 0) {
        if (write < arr.size) {
            arr[write] = arr[read]
        }

        if (arr[read] == 0) {
            write--
            if (write < arr.size) {
                arr[write] = 0
            }
        }

        read--
        write--
    }
}

왜 오른쪽에서부터 써야 하나요?

예를 들어 앞에서부터 직접 쓰면 이런 문제가 생깁니다.

arr = [1, 0, 2, 3]

0을 복제하려고 arr[2]에 0을 쓰는 순간, 원래 있던 2를 아직 읽기도 전에 잃어버립니다.

반면 뒤에서부터 쓰면:

• 이미 읽은 값만 오른쪽에 배치하게 되고
• 아직 읽지 않은 왼쪽 값은 건드리지 않습니다

이 문제는 "오른쪽으로 밀어내는" 구조라서, 제자리로 하려면 뒤에서 처리하는 쪽이 자연스럽습니다.

예제로 따라가기

arr = [1, 0, 2, 3, 0, 4, 5, 0]를 보겠습니다.

먼저 0의 개수는 3개입니다.

실제 길이 = 8
가상 길이 = 8 + 3 = 11
read = 7
write = 10

이제 뒤에서부터 진행합니다.

read=7, arr[7]=0
write=10 -> 범위 밖이라 실제로는 안 씀
0이므로 한 칸 더 write-- 해서 복제용 0도 처리

read=6, arr[6]=5
가상 위치 write=8 -> 범위 밖, 실제로는 안 씀

read=5, arr[5]=4
가상 위치 write=7 -> arr[7] = 4

read=4, arr[4]=0
가상 위치 write=6 -> arr[6] = 0
복제용 write=5 -> arr[5] = 0

read=3, arr[3]=3
write=4 -> arr[4] = 3

read=2, arr[2]=2
write=3 -> arr[3] = 2

read=1, arr[1]=0
write=2 -> arr[2] = 0
복제용 write=1 -> arr[1] = 0

read=0, arr[0]=1
write=0 -> arr[0] = 1

최종 결과:

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

입니다.

여기서 중요한 점은 write가 배열 길이 밖에 있을 때는 그냥 무시한다는 것입니다. 어차피 그 값들은 "고정 길이 때문에 잘려 나갈 값"이기 때문입니다.

시간과 공간 복잡도

Phase 2는:

• 한 번 순회하며 0 개수 세기
• 한 번 역순 순회하며 실제 쓰기

를 합니다.

따라서 시간 복잡도는 O(n)입니다. 추가 배열 없이 포인터와 카운터만 쓰므로 공간 복잡도는 O(1)입니다.

엣지 케이스

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

입력	결과	이유
[1, 2, 3]	[1, 2, 3]	0이 없으면 그대로
[0]	[0]	길이 1에서는 복제해도 하나만 남음
[0, 1]	[0, 0]	1이 오른쪽으로 밀려 잘림
[1, 0]	[1, 0]	마지막 0의 복제분은 배열 밖으로 나감
[1, 0, 2, 3, 0, 4, 5, 0]	[1, 0, 0, 2, 3, 0, 0, 4]	기본 예시

특히 [1, 0]이 중요합니다. 0을 복제해야 하지만 배열 길이가 고정이므로, 두 번째 0은 보이지 않고 버려집니다.

두 풀이를 다시 비교

풀이	시간	공간	특징
별도 배열에 결과 생성	O(n)	O(n)	직관적이지만 제자리 조건을 만족하지 못함
오른쪽에서부터 제자리 덮어쓰기	O(n)	O(1)	가상 길이를 기준으로 뒤에서 써서 원본 훼손 없이 처리

마무리

1. 이 문제는 0을 없애는 문제가 아니라 복제하는 문제입니다 — 그래서 Move Zeroes와는 구조가 다릅니다
2. 배열 길이가 고정이라 뒤로 밀려난 값 일부는 버려집니다 — 가상의 결과 전체를 다 저장할 수는 없습니다
3. 앞에서부터 제자리 쓰기를 하면 아직 읽지 않은 값을 덮어쓸 수 있습니다 — 그래서 오른쪽에서부터 처리해야 합니다
4. 가상 배열의 끝을 생각하고, 실제 배열 범위 안에 들어오는 값만 쓰면 됩니다 — write < arr.size 조건이 이 역할을 합니다
5. 최종 제자리 풀이는 O(n) 시간, O(1) 공간입니다 — 문제의 핵심은 "복제 후 밀림"을 뒤에서 안전하게 반영하는 데 있습니다