LeetCode Solution: 283. Move Zeroes

Context

배열에서 0을 끝으로 이동시키되 비영(非零) 원소의 상대적 순서를 유지하면서 제자리(in-place) 수정해야 하는 배열 조작 문제이다. 직관적인 접근(0을 찾아 제거하고 추가)은 O(N²) 복잡도를 초래한다.

Technical Solution

• 관점 전환: 0을 끝으로 이동시키는 대신 비영 원소를 앞으로 이동시키는 방식으로 재설계
• 두 포인터 기법 도입: nonZeroPtr(비영 원소 삽입 위치)과 i(현재 탐색 위치) 사용
• 배열을 두 섹션으로 논리 분할: 비영 원소가 들어갈 "Good" 섹션(앞부분)과 나머지 부분
• 스왑(swap) 연산으로 제자리 수정: nums[i]와 nums[nonZeroPtr]을 교환하여 상대적 순서 유지
• 단일 순회: i 포인터로 배열을 한 번만 탐색하면서 각 원소를 O(1)에 처리

Impact

시간복잡도 O(N), 공간복잡도 O(1) 달성으로 메모리 제약 환경에서 최적화된 솔루션 제공

Key Takeaway

두 포인터 기법은 제자리 배열 조작 문제의 핵심 패턴이며, 문제를 역으로 생각하는 관점의 전환이 단순하고 효율적인 알고리즘 설계로 이어질 수 있다.