양수와 음수가 섞여 있는 정수형 배열 arr[]가 주어졌을 때, 상수 크기의 추가 공간(O(1) 메모리)만 사용해 배열 내부에서 양수와 음수를 재배열하고 그 결과를 출력하는 것이 이 글의 목표입니다.
이 문제는 완전한 정렬이 아니라 '음수는 앞쪽에, 양수는 뒤쪽에 배치'하는 분할(partition) 작업이므로, 추가 배열 없이 두 포인터(two pointer) 기법만으로 효율적으로 해결할 수 있습니다. 이 방식은 퀵 정렬(Quick Sort)의 파티션 단계와 원리가 유사합니다.
입출력 시나리오 살펴보기
입력 − int arr[] = {4, 2, -1, -1, 6, -3, 0}
출력 − 상수 추가 공간으로 양수와 음수를 재배열한 결과: -3 -1 -1 0 6 2 4
설명 − 크기가 7인 정수 배열에 양수와 음수가 함께 들어 있습니다. 추가 공간을 사용하지 않고 배열 내부에서 음수를 앞으로, 양수를 뒤로 옮기면 최종 결과는 -3 -1 -1 0 6 2 4가 됩니다.
입력 − int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}
출력 − 상수 추가 공간으로 양수와 음수를 재배열한 결과: -9 -10 2 3 10 5 8 4
설명 − 크기가 8인 정수 배열입니다. 이 경우 음수가 이미 배열 앞쪽에 모여 있어 교환(swap)이 발생하지 않으며, 따라서 원래 순서가 그대로 유지됩니다.
알고리즘 접근 방식
정수형 배열을 입력받고 배열의 크기를 계산합니다.
FOR 반복문을 사용해 재배열 전 배열의 상태를 출력합니다.
배열과 배열의 크기를 매개변수로 전달하며 Rearrangement(arr, size) 함수를 호출합니다.
Rearrangement(arr, size) 함수 내부에서 다음을 수행합니다.
정수형 변수 i를 0으로, j를 size - 1로 선언합니다. i는 왼쪽부터, j는 오른쪽부터 탐색합니다.
while(true) 무한 루프를 시작합니다.
arr[i]가 0보다 작고 i가 size보다 작은 동안 i를 1씩 증가시켜, 음수가 아닌 첫 번째 위치를 찾습니다.
arr[j]가 0보다 크고 j가 0 이상인 동안 j를 1씩 감소시켜, 양수가 아닌 마지막 위치를 찾습니다.
i가 j보다 작으면 temp 변수를 이용해 arr[i]와 arr[j]의 값을 서로 교환(swap)합니다.
그렇지 않으면(i ≥ j) break로 루프를 종료합니다. 이 시점에는 음수가 모두 앞쪽에, 양수가 모두 뒤쪽에 배치된 것입니다.
재배열이 완료된 결과를 출력합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
void Rearrangement(int arr[], int size){
int i = 0;
int j = size - 1;
while(true){
while(arr[i] < 0 && i < size){
i++;
}
while(arr[j] > 0 && j >= 0){
j--;
}
if (i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else{
break;
}
}
}
int main(){
int arr[] = {4, 2, -1, -1, 6, -3, 0};
int size = sizeof(arr)/sizeof(arr[0]);
//배열을 재배열하는 함수 호출
Rearrangement(arr, size);
//재배열 후 배열 출력
cout<<"상수 추가 공간으로 양수와 음수를 재배열한 결과: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
상수 추가 공간으로 양수와 음수를 재배열한 결과: -3 -1 -1 0 6 2 4
복잡도 분석
두 포인터 i와 j가 배열을 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, 교환에 사용되는 temp 변수 하나만 필요하므로 공간 복잡도는 O(1), 즉 상수 개의 추가 공간만 사용합니다. 추가 버퍼나 STL의 sort 함수 없이도 문제를 해결할 수 있다는 점이 이 접근 방식의 가장 큰 장점입니다.