정수 배열 nums가 주어졌을 때, 0이 아닌 원소들의 상대적 순서는 그대로 유지하면서 모든 0을 배열의 뒤쪽으로 옮기는 문제.
새 배열을 만들지 않고 주어진 배열을 그 자리에서(in-place) 수정해야함.
입력: nums = [0, 1, 0, 3, 12]
출력: [1, 3, 12, 0, 0]처음 떠올린 방법: remove + append
가장 직관적인 접근은 "0을 만나면 지우고, 맨 뒤에 다시 붙이자"
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
zeros = nums.count(0)
for _ in range(zeros):
nums.remove(0) # 앞에서부터 첫 번째 0을 제거
nums.append(0) # 맨 뒤에 0을 추가동작 자체는 맞으나.
0을 하나 빼서 뒤에 붙이는 걸 0의 개수만큼 반복하면, 0이 아닌 값들은 순서를 유지한 채 앞으로 당겨지고 0은 뒤에 모인다.
문제는 시간 복잡도!
왜 O(n²)일까?
핵심은 파이썬 리스트에서 remove()가 O(n) 연산이라는 점입니다.
list.remove(0)은 두 가지 일을 합니다.
- 앞에서부터 값을 찾을 때까지 훑는다. (탐색)
- 찾은 위치의 원소를 지운 뒤, 그 뒤에 있던 모든 원소를 한 칸씩 앞으로 당긴다. (이동)
특히 2번의 "한 칸씩 당기기" 때문에 최악의 경우 원소를 n개 옮겨야 합니다. 즉 remove() 한 번이 O(n)입니다.
이걸 0의 개수만큼(최악의 경우 n번) 반복하니까:
O(n) × n번 = O(n²)append()는 분할 상환(amortized) O(1)이라 부담이 아니지만, 반복되는 remove()가 전체를 O(n²)로 끌어올립니다.
배열이 [0, 0, 0, ..., 0, 1]처럼 0이 많은 경우 특히 느려집니다.
참고로, 리스트를 순회하면서 동시에 remove()로 원소를 지우면 인덱스가 밀려서 원소를 건너뛰는 버그도 생기기 쉽습니다. count()로 개수를 먼저 세는 방식은 이 버그는 피하지만, O(n²)라는 성능 문제는 그대로 남습니다.
개선: 투 포인터 (O(n))
remove가 원소를 계속 밀어내는 게 문제였으니, 밀어내지 말고 자리만 맞바꾸면(swap) 됩니다. 여기서 포인터 두 개를 사용합니다.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
a = 0 # 다음 non-zero를 넣을 자리 (느린 포인터)
for b in range(len(nums)): # 배열을 훑는 포인터 (빠른 포인터)
if nums[b] != 0:
nums[a], nums[b] = nums[b], nums[a] # 교환
a += 1두 포인터의 역할
- b (빠른 포인터): 배열을 처음부터 끝까지 한 번 훑기만 합니다. 매 칸에서 "0이야, 아니야?"만 판단합니다.
- a (느린 포인터): "다음 non-zero가 들어갈 자리" 를 가리키는 커서입니다. b가 0이 아닌 값을 찾을 때마다 그 값을 a 자리로 가져오고 a를 한 칸 전진시킵니다.
포인트는 a는 non-zero를 만났을 때만 움직인다는 것입니다. 0을 만나면 a는 멈춰 있고 b만 앞서 나갑니다. 그래서 a와 b 사이에 벌어진 간격이 정확히 "지금까지 지나온 0의 개수"가 됩니다.
마무리
- 파이썬 리스트에서 remove(), insert(), pop(0) 같은 연산은 내부적으로 원소를 밀어내기 때문에 O(n)입니다. 반복문 안에서 쓰면 O(n²)이 되기 쉽습니다.
- "지우고 다시 넣기" 대신 자리를 맞바꾸는(swap) 발상으로 바꾸면 이동 비용을 없앨 수 있습니다.