제로 이동 — 읽기 및 쓰기 포인터 패턴 이해 (C++)

Source: Dev.to

Problem Summary

정수 배열 nums가 주어집니다. 제자리(in‑place) 에서 모든 0을 배열의 끝으로 이동시키면서, 0이 아닌 요소들의 상대적인 순서는 유지하세요.

Example

• Input: [0, 1, 0, 3, 12]
• Output: [1, 3, 12, 0, 0]

Key Intuition

이 문제는 두 개의 포인터(읽기/쓰기) 패턴으로 해결할 수 있습니다:

• rd (read pointer) – 배열을 왼쪽에서 오른쪽으로 스캔합니다.
• wrt (write pointer) – 다음에 0이 아닌 요소를 놓을 위치를 표시합니다.

nums[rd]가 0이 아니면 nums[wrt]와 교환하고 wrt를 증가시킵니다.
rd는 항상 앞으로 이동하고, wrt는 0이 아닌 요소를 찾을 때만 이동합니다.
그 결과 모든 0은 자연스럽게 끝으로 밀려납니다.

Solution (C++)

class Solution {
public:
    void moveZeroes(vector& nums) {
        int wrt = 0, rd = 0;

        while (rd < nums.size()) {
            if (nums[rd] != 0) {
                swap(nums[wrt], nums[rd]);
                ++wrt;
            }
            ++rd;
        }
    }
};

Walkthrough Example

nums = [0, 1, 0, 3, 12] 를 고려해 보겠습니다.

루프가 끝난 후:

• 모든 0이 아닌 요소가 원래 순서를 유지한 채 앞쪽에 위치합니다.
• 0은 끝으로 밀려났습니다.

Complexity Analysis

• Time: O(n) – 각 요소를 한 번씩 검사합니다.
• Space: O(1) – 두 개의 정수 포인터만 사용합니다.

Takeaways

• 읽기/쓰기 포인터 패턴은 제자리 배열 조작에 강력한 도구입니다.
• 유효한 요소를 올바르게 배치하는 데 집중하면, “무효” 요소(0)는 자동으로 제자리를 찾게 됩니다.
• 이 패턴은 요소 제거나 데이터 압축과 같은 다른 배열 문제에서도 자주 등장합니다.
• 이를 숙달하면 많은 DSA 문제를 간단하고 효율적인 코드로 해결할 수 있습니다.