Move Zeroes — 쓰기 포인터 하나로 `O(n)`/`O(1)` 제자리 재배치

0을 뒤로 밀기, 어떤 문제인가요?

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

정수 배열 nums가 주어졌을 때, 모든 0을 배열의 끝으로 이동하세요. 0이 아닌 원소의 상대적 순서는 유지해야 하며, 배열을 제자리(in-place) 에서 수정해야 합니다.

예시는 이렇습니다.

• nums = [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]
• nums = [0] → [0]

제약은 다음과 같습니다.

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

"0을 뒤로 민다"는 말을 뒤집으면 **"0이 아닌 원소를 앞으로 모은다"**는 뜻입니다. 이 글에서는 별도 배열을 쓰는 방식부터, 쓰기 포인터 하나로 제자리 스왑하는 방식까지 비교합니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

Phase 1. 별도 배열에 모아서 복사

가장 직관적인 접근은 0이 아닌 원소만 새 배열에 순서대로 모은 뒤, 나머지를 0으로 채우는 것입니다.

fun moveZeroes(nums: IntArray) {
    val result = IntArray(nums.size)
    var idx = 0

    for (num in nums) {
        if (num != 0) result[idx++] = num
    }

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

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

• 0이 아닌 원소 수집: result = [1, 3, 12, 0, 0]
• 원본에 복사: nums = [1, 3, 12, 0, 0]

정답은 맞지만, result 배열에 O(n) 추가 공간이 필요합니다. 문제가 요구하는 제자리(in-place) 조건을 만족하지 못합니다.

Phase 2. 쓰기 포인터 스왑 — 제자리 한 번 훑기

별도 배열 없이 하려면, 같은 배열 위에서 "다음에 0이 아닌 값을 쓸 위치"를 가리키는 write 포인터를 하나 둡니다. 0이 아닌 원소를 만날 때마다 write 위치와 스왑하면, 0이 자연스럽게 뒤쪽으로 밀립니다.

fun moveZeroes(nums: IntArray) {
    var write = 0

    for (read in nums.indices) {
        if (nums[read] != 0) {
            val temp = nums[write]
            nums[write] = nums[read]
            nums[read] = temp
            write++
        }
    }
}

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

초기: [0, 1, 0, 3, 12]
       W  R

read=0: nums[0]=0 → 건너뜀

read=1: nums[1]=1 ≠ 0 → nums[0]↔nums[1]
  [1, 0, 0, 3, 12]   write=1
      W     R

read=2: nums[2]=0 → 건너뜀

read=3: nums[3]=3 ≠ 0 → nums[1]↔nums[3]
  [1, 3, 0, 0, 12]   write=2
         W        R

read=4: nums[4]=12 ≠ 0 → nums[2]↔nums[4]
  [1, 3, 12, 0, 0]   write=3

결과: [1, 3, 12, 0, 0] ✓

시간 O(n), 공간 O(1)입니다.

왜 0이 아닌 원소의 순서가 유지되나요?

write 포인터는 0이 아닌 원소를 만날 때만 전진합니다. 배열을 왼쪽부터 읽으면서, 0이 아닌 원소를 만나는 순서 그대로 write 위치에 기록하므로 상대적 순서가 보존됩니다.

write와 read가 같은 위치일 때는?

배열 앞부분에 0이 없으면 write와 read가 함께 움직입니다. 예를 들어 [1, 2, 0, 3]에서:

• read = 0: nums[0] = 1 ≠ 0 → nums[0]↔nums[0] (자기 자신과 스왑), write = 1
• read = 1: nums[1] = 2 ≠ 0 → nums[1]↔nums[1], write = 2

자기 자신과의 스왑은 결과에 영향을 주지 않습니다. 불필요한 쓰기를 줄이고 싶다면 if (read != write) 조건을 추가할 수 있습니다.

fun moveZeroes(nums: IntArray) {
    var write = 0

    for (read in nums.indices) {
        if (nums[read] != 0) {
            if (read != write) {
                nums[write] = nums[read]
                nums[read] = 0
            }
            write++
        }
    }
}

이 버전은 read == write일 때 아무 쓰기도 하지 않으므로, 0이 적은 배열에서 불필요한 메모리 쓰기를 줄여 줍니다.

참고: 이 쓰기 포인터 패턴은 String Compression의 읽기/쓰기 포인터와 같은 원리입니다. read는 원본을 훑고, write는 결과를 기록하며, 결과가 원본보다 짧거나 같을 때 같은 배열 위에서 안전하게 동작합니다.

두 풀이를 다시 비교

풀이	시간	공간	특징
별도 배열 복사	O(n)	O(n)	직관적이지만 제자리 조건 위반
쓰기 포인터 스왑	O(n)	O(1)	한 번 훑기로 0을 뒤로 밀면서 순서 유지

마무리

1. "0을 뒤로 민다"는 "0이 아닌 원소를 앞으로 모은다"로 바꿔 생각하면 쓰기 포인터가 자연스럽게 나온다 — 비교 대상이 0이라는 것만 다를 뿐, "조건을 만족하는 원소를 앞으로 압축"하는 일반 패턴입니다
2. write는 "다음에 값을 쓸 위치"를 추적하고, read는 원본을 순서대로 훑는다 — 이 역할 분리가 상대적 순서 보존을 보장합니다
3. read != write일 때만 쓰기를 수행하면 불필요한 메모리 접근을 줄일 수 있다 — 0이 적은 입력에서 효과가 큽니다