문제 설명
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 우리는 리스트를 제자리(in-place)에서 직접 수정하여 모든 0을 리스트의 끝으로 옮겨야 합니다. 이때 나머지 요소들의 상대적인 순서는 그대로 유지되어야 하며, O(1)의 추가 공간만 사용해 문제를 해결하는 것이 목표입니다.
예를 들어 입력이 [2,0,1,4,0,5,6,4,0,1,7]이라면, 출력은 다음과 같습니다.
[2, 1, 4, 5, 6, 4, 1, 7, 0, 0, 0]
풀이 접근 방법
핵심 아이디어는 매우 간단합니다. 0이 아닌 요소들을 앞쪽부터 차례대로 재배치한 뒤, 남은 뒷부분의 자리를 모두 0으로 채우는 것입니다. 이를 위해 다음 단계를 따릅니다.
- 리스트 L의 길이가 0이면 빈 리스트를 그대로 반환합니다.
- k := 0으로 초기화합니다. k는 다음에 채워질 위치를 가리키는 포인터 역할을 합니다.
- i를 0부터 L의 길이까지 순회하며, 만약 L[i]가 0이 아니라면 L[k] := L[i]로 값을 복사하고 k를 1 증가시킵니다.
- j를 k부터 L의 길이까지 순회하며, 해당 위치들을 L[j] := 0으로 설정합니다.
- 수정된 리스트 L을 반환합니다.
이렇게 하면 원본 리스트 하나만 사용해 0이 아닌 요소들의 순서를 유지하면서 0을 뒤로 밀어낼 수 있습니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
class Solution: def solve(self, L): if len(L) == 0: return [] k = 0 for i in range(len(L)): if L[i] != 0: L[k] = L[i] k+=1 for j in range(k,len(L)): L[j] = 0 return L ob = Solution() L = [2,0,1,4,0,5,6,4,0,1,7] print(ob.solve(L))
입력
[2,0,1,4,0,5,6,4,0,1,7]
출력
[2, 1, 4, 5, 6, 4, 1, 7, 0, 0, 0]
복잡도 분석
시간 복잡도: O(n) — 리스트를 최대 두 번 순회하므로 실행 시간은 요소 개수 n에 비례합니다.
공간 복잡도: O(1) — 인덱스 변수 몇 개만 사용하므로 추가 공간은 상수 수준으로 유지됩니다.