양수와 음수가 모두 포함된 정수형 배열 arr[]가 주어졌다고 가정해 보겠습니다. 이때 우리의 과제는 모든 양수와 음수가 교대로 배치되도록 배열을 재배열하는 것입니다. 만약 어느 한쪽 부호의 요소가 남게 된다면, 남은 요소들은 배열의 맨 끝에 배치하면 됩니다.
입력·출력 시나리오 살펴보기
입력 − int arr[] = {4, 2, -1, -1, 6, -3}
출력 − O(n) 시간과 O(1) 추가 공간으로 양수와 음수를 재배열한 결과: 2 -1 6 -1 4 -3
설명 − 크기가 6인 정수 배열에 양수와 음수 요소가 함께 들어 있습니다. 모든 양수와 음수가 교대로 위치하도록 배열을 재배열하고, 남는 요소들은 배열 끝에 배치합니다. 따라서 최종 결과는 2 -1 6 -1 4 -3이 됩니다.
입력 − int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}
출력 − O(n) 시간과 O(1) 추가 공간으로 양수와 음수를 재배열한 결과: 2 -2 3 -5 5 -3 5 -1 1 3 1 1
설명 − 크기가 12인 정수 배열에 양수와 음수 요소가 함께 들어 있습니다. 마찬가지로 양수와 음수가 번갈아 나타나도록 재배열한 뒤, 남는 요소들을 배열 끝에 배치하면 최종 결과는 2 -2 3 -5 5 -3 5 -1 1 3 1 1이 됩니다.
알고리즘이 동작하는 원리
이 접근 방식은 두 단계로 나누어 이해할 수 있습니다.
1단계 — 음수 분리: 배열을 한 번 순회하면서 음수를 발견할 때마다 포인터 temp를 앞으로 옮기며 해당 값과 swap합니다. 이 과정이 끝나면 모든 음수가 배열 앞쪽에, 양수는 뒤쪽에 모이게 됩니다.
2단계 — 교대 배치: 음수 영역의 짝수 인덱스 위치와 양수 영역의 값을 차례로 swap하여 양수와 음수가 번갈아 나타나도록 만듭니다.
두 단계 모두 상수 개의 변수만 사용해 배열을 한 번씩 순회하므로, 전체 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)입니다.
프로그램에서 사용하는 접근 방식
정수형 요소로 이루어진 배열을 입력받고 배열의 크기를 계산합니다.
FOR 루프를 사용해 재배열 작업 전의 배열 상태를 출력합니다.
배열과 배열의 크기를 매개변수로 전달하며 Rearrangement(arr, size) 함수를 호출합니다.
Rearrangement(arr, size) 함수 내부에서는 다음과 같이 동작합니다.
임시 정수형 변수 temp를 -1로 선언하고, positive는 temp + 1로, negative는 0으로 초기화합니다.
i가 0부터 배열 크기 미만일 때까지 FOR 루프를 수행합니다. 루프 안에서 arr[i]가 0보다 작은지 검사하고, 조건이 참이면 temp를 1 증가시킨 뒤 C++ STL의 내장 함수인 swap(arr[temp], arr[i])를 호출해 두 값을 맞바꿉니다.
positive가 배열 크기보다 작고, negative가 positive보다 작으며, arr[negative]가 0보다 작은 동안 WHILE 루프를 수행합니다. 루프 안에서는 arr[negative]와 arr[positive]를 swap으로 맞바꾸고, positive를 1 증가시킨 뒤 negative를 negative + 2로 갱신합니다.
최종 결과를 출력합니다.
예제
#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
int temp = -1;
for(int i = 0; i < size; i++){
if (arr[i] < 0){
temp++;
swap(arr[temp], arr[i]);
}
}
int positive = temp + 1;
int negative = 0;
while(positive < size && negative < positive && arr[negative] < 0){
swap(arr[negative], arr[positive]);
positive++;
negative = negative + 2;
}
}
int main(){
int arr[] = {4, 2, -1, -1, 6, -3};
int size = sizeof(arr)/sizeof(arr[0]);
//배열을 재배열하는 함수 호출
Rearrangement(arr, size);
//재배열 후 배열 출력
cout<<"O(n) 시간과 O(1) 추가 공간으로 양수와 음수를 재배열한 결과: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
O(n) 시간과 O(1) 추가 공간으로 양수와 음수를 재배열한 결과: 2 -1 6 -1 4 -3