문제 개요
숫자들을 담고 있는 배열이 있다고 가정해 보겠습니다. 배열에는 0이 아닌 값과 0이 섞여 있으며, 우리의 목표는 다른 숫자들의 상대적인 순서를 유지하면서 모든 0을 배열의 오른쪽 끝으로 이동시키는 것입니다.
예를 들어, 배열이 [0, 1, 5, 0, 3, 8, 0, 0, 9]라면 최종 결과는 [1, 5, 3, 8, 9, 0, 0, 0, 0]이 되어야 합니다.
해결 접근 방식
이 문제는 두 단계로 나누어 해결할 수 있습니다.
- 0이 아닌 값 앞쪽으로 모으기: 삽입 위치를 나타내는 인덱스(index)를 0으로 초기화합니다. 그리고 배열을 처음부터 끝까지 순회하면서, 현재 값이 0이 아니면 해당 값을 index 위치에 저장하고 index를 1 증가시킵니다.
- 나머지 자리를 0으로 채우기: 첫 번째 순회가 끝난 후, index 위치부터 배열의 끝까지 모든 요소를 0으로 설정합니다.
이 방법은 시간 복잡도 O(n), 공간 복잡도 O(1)로 효율적이며, 원본 배열을 직접 수정(in-place)한다는 특징이 있습니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
insert_index = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[insert_index] = nums[i]
insert_index += 1
for i in range(insert_index, len(nums)):
nums[i] = 0
nums = [0,1,5,0,3,8,0,0,9]
ob1 = Solution()
ob1.moveZeroes(nums)
print(nums)입력
nums = [0,1,5,0,3,8,0,0,9]
출력
[1,5,3,8,9,0,0,0,0]
동작 과정 살펴보기
위 코드가 실행되는 과정을 단계별로 확인해 보겠습니다.
- 배열을 순회하면서 0이 아닌 값(1, 5, 3, 8, 9)을 차례대로 배열의 앞부분에 배치합니다.
- 순회가 완료되면 insert_index는 5가 되며, 배열의 앞 5자리는 [1, 5, 3, 8, 9]로 채워집니다.
- 마지막으로 인덱스 5부터 배열 끝까지를 0으로 덮어써서 [1, 5, 3, 8, 9, 0, 0, 0, 0]이라는 최종 결과를 얻습니다.
마무리
이 알고리즘은 추가 배열을 사용하지 않고 제자리에서 해결하기 때문에 메모리 효율성이 뛰어납니다. 배열 내에서 특정 조건의 요소를 재배치하는 다양한 문제(예: 짝수와 홀수 분리, 특정 값 제거 등)에도 동일한 패턴을 응용할 수 있으므로, 코딩 테스트 준비에 꼭 익혀두면 좋은 기법입니다.