여러 개의 0이 포함된 배열이 주어졌을 때, 배열에 있는 모든 0을 배열의 끝으로 이동해야 합니다. 예시를 통해 자세히 살펴보겠습니다.
입력
arr = [4, 5, 0, 3, 2, 0, 0, 0, 5, 0, 1]
출력
4 5 3 2 5 1 0 0 0 0 0
알고리즘
배열을 초기화합니다.
인덱스 변수를 0으로 초기화합니다.
주어진 배열을 처음부터 끝까지 순회합니다.
현재 요소가 0이 아니라면, 해당 인덱스 위치에 현재 요소의 값을 저장합니다.
인덱스를 1 증가시킵니다.
위에서 갱신된 인덱스부터 n까지 반복하는 루프를 작성합니다.
해당 구간의 모든 요소를 0으로 설정합니다.
이 방식은 0이 아닌 요소들을 앞쪽으로 차례대로 옮긴 뒤, 남은 자리를 모두 0으로 채우는 원리입니다. 결과적으로 0이 아닌 요소들의 상대적 순서는 그대로 유지됩니다.
구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void moveZeroesToEnd(int arr[], int n) {
int index = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
arr[index++] = arr[i];
}
}
while (index < n) {
arr[index++] = 0;
}
}
int main() {
int arr[] = {4, 5, 0, 3, 2, 0, 0, 0, 5, 0, 1};
int n = 11;
moveZeroesToEnd(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 확인할 수 있습니다.
4 5 3 2 5 1 0 0 0 0 0
복잡도 분석
시간 복잡도: O(n) — 배열을 단 한 번 순회하므로 선형 시간이 소요됩니다.
공간 복잡도: O(1) — 추가 메모리 없이 배열 내부에서 직접(in-place) 처리하므로 상수 공간만 사용합니다.