이 튜토리얼에서는 배열 안의 모든 0은 앞쪽으로, 1은 뒤쪽으로 이동시키는 프로그램을 C++로 작성해 보겠습니다.
문제는 다음과 같습니다. 0과 1이 섞여 있는 임의의 정수 배열이 주어졌을 때, 모든 0은 배열의 시작 부분으로, 모든 1은 배열의 끝 부분으로 이동해야 합니다. 나머지 숫자들은 원래 순서를 유지한 채 가운데에 배치됩니다.
예를 들어 살펴보겠습니다.
입력
arr = [4, 5, 1, 1, 0, 0, 2, 0, 3, 1, 0, 1]
출력
0 0 0 0 4 5 2 3 1 1 1 1
알고리즘
핵심 아이디어는 두 단계로 나누어 처리하는 것입니다. 먼저 1을 뒤로 밀어내고, 그다음 0을 앞으로 당기는 방식입니다.
- 배열을 초기화합니다.
- 인덱스 변수를 하나 선언하고 0으로 설정합니다.
- 주어진 배열을 처음부터 끝까지 순회하면서 다음을 수행합니다.
- 현재 요소가 1이 아니라면, 인덱스 위치에 해당 요소를 저장하고 인덱스를 증가시킵니다.
- 순회가 끝난 후, 위에서 기록한 인덱스부터 배열의 끝(n)까지 반복하면서 모든 요소를 1로 채웁니다. 이렇게 하면 1이 모두 뒤쪽으로 이동합니다.
- 같은 방식으로 0도 처리합니다. 이번에는 배열을 뒤에서 앞으로 순회하면서, 인덱스를 감소시켜 0을 모두 앞쪽으로 이동시킵니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 추가적인 배열 없이 제자리(in-place)에서 수행되므로 공간 복잡도는 O(1)입니다.
구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void update1And0Positions(int arr[], int n) {
int index = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 1) {
arr[index++] = arr[i];
}
}
while (index < n) {
arr[index++] = 1;
}
index = 0;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] == 1) {
continue;
}
if (!index) {
index = i;
}
if (arr[i] != 0) {
arr[index--] = arr[i];
}
}
while (index >= 0) {
arr[index--] = 0;
}
}
int main() {
int arr[] = { 4, 5, 1, 1, 0, 0, 2, 0, 3, 1, 0, 1 };
int n = 12;
update1And0Positions(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
0 0 0 0 4 5 2 3 1 1 1 1
출력에서 확인할 수 있듯이, 모든 0은 배열의 앞쪽에, 모든 1은 배열의 뒤쪽에 배치되었으며, 나머지 숫자들(4, 5, 2, 3)은 상대적인 순서를 유지한 채 가운데에 위치하게 됩니다.