양수와 음수가 뒤섞여 있는 정수형 배열 arr[]가 주어졌을 때, C++ STL에서 제공하는 내장 sort() 함수를 사용하거나 재귀(recursion) 호출 기법을 활용하여 배열의 요소들을 재배치하고 그 결과를 출력하는 것이 이번 글의 목표입니다. 여기서 말하는 재배치란 모든 음수 요소가 양수 요소보다 앞쪽에 오도록 순서를 바꾸는 것을 의미합니다.
입력·출력 시나리오 살펴보기
입력 − int arr[] = {4, 2, -1, -1, 6, -3, 0}
출력 − 내장 sort 함수를 사용해 재정렬한 결과: -3 -1 -1 0 2 4 6
설명 − 크기가 7인 정수 배열에 양수와 음수가 함께 들어 있습니다. 모든 음수 요소가 양수 요소보다 앞에 오도록 배열을 재정렬하면 최종 결과는 -3 -1 -1 0 2 4 6이 됩니다.
입력 − int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}
출력 − 내장 sort 함수를 사용해 재정렬한 결과: -10 -9 2 3 4 5 8 10
설명 − 크기가 8인 정수 배열에 양수와 음수가 함께 들어 있습니다. 모든 음수 요소가 양수 요소보다 앞에 오도록 배열을 재정렬하면 최종 결과는 -10 -9 2 3 4 5 8 10이 됩니다.
프로그램에서 사용된 접근 방식
방법 1: sort() 함수 사용
정수형 요소로 구성된 배열을 입력받고 배열의 크기를 계산합니다.
배열과 크기를 Rearrangement(int arr[], int size) 함수에 전달합니다.
함수 내부에서는 배열과 배열의 크기를 인자로 넘겨 C++ STL의 sort() 함수를 호출합니다. 이 함수는 배열을 오름차순으로 정렬해 줍니다.
결과를 출력합니다.
방법 2: 재귀 호출 사용
정수형 배열을 입력받고 배열의 크기를 계산합니다.
임시 변수(예: temp)를 선언합니다.
i부터 배열 크기 미만까지 반복문을 수행하면서, arr[i]가 0보다 작으면 temp를 1씩 증가시켜 음수의 개수를 셉니다.
배열, 0, size - 1을 인자로 전달하며 Rearrangement(arr, 0, size - 1) 함수를 호출합니다.
배열, temp, size - 1을 인자로 전달하며 Rotate 함수를 호출합니다.
Rearrangement(int arr[], int first, int last) 함수 내부에서는 다음을 수행합니다.
first == last이면 그대로 반환합니다.
first + 1과 last를 인자로 전달하며 Rearrangement() 함수를 재귀적으로 호출합니다.
arr[first]가 0보다 크거나 같으면 Rotate(arr, first + 1, last)와 Rotate(arr, first, last)를 차례로 호출합니다.
Rotate(int arr[], int first, int last) 함수 내부에서는 다음을 수행합니다.
first < last인 동안 반복하면서 temp에 arr[first]를 저장하고, arr[first] = arr[last], arr[last] = temp로 값을 교환한 뒤 first는 1 증가, last는 1 감소시킵니다. 즉, 해당 구간의 요소들을 뒤집습니다.
결과를 출력합니다.
1. sort() 함수 사용 예제
#include <bits/stdc++.h>
using namespace std;
// sort() 함수를 사용하는 방식
void Rearrangement(int arr[], int size){
sort(arr, arr + size);
}
int main(){
int arr[] = {4, 2, -1, -1, 6, -3, 0};
int size = sizeof(arr)/sizeof(arr[0]);
// 배열을 재정렬하기 위해 함수 호출
Rearrangement(arr, size);
// 값 재정렬 후 배열 출력
cout<<"내장 sort 함수를 사용한 양수·음수 재정렬 결과: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
내장 sort 함수를 사용한 양수·음수 재정렬 결과: -3 -1 -1 0 2 4 6
2. 재귀 호출을 사용한 예제
#include <bits/stdc++.h>
using namespace std;
void Rotate(int arr[], int first, int last){
while(first < last){
int temp = arr[first];
arr[first] = arr[last];
arr[last] = temp;
first++;
last--;
}
}
void Rearrangement(int arr[], int first, int last){
if(first == last){
return;
}
Rearrangement(arr, (first + 1), last);
if(arr[first] >= 0){
Rotate(arr, (first + 1), last);
Rotate(arr, first, last);
}
}
int main(){
int arr[] = {4, 2, -1, -1, 6, -3, 0};
int size = sizeof(arr)/sizeof(arr[0]);
int temp = 0;
// 음수의 개수를 셈
for(int i = 0; i < size; i++){
if(arr[i] < 0){
temp++;
}
}
// 배열을 재정렬하기 위해 함수 호출
Rearrangement(arr, 0, (size - 1));
Rotate(arr, temp, (size - 1));
// 값 재정렬 후 배열 출력
cout<<"재귀를 사용한 양수·음수 재정렬 결과: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
재귀를 사용한 양수·음수 재정렬 결과: -1 -1 -3 4 2 6 0
두 방법의 차이점
sort() 함수를 사용하는 방법은 배열 전체를 오름차순으로 완전히 정렬하므로 시간 복잡도는 O(n log n)입니다. 반면 재귀 방식은 음수를 모두 양수보다 앞쪽으로 이동시키는 분할(partition) 역할만 수행하며, 각 그룹 내부의 상대적인 순서까지 완전히 정렬하지는 않습니다. 따라서 위 출력에서도 음수(-1, -1, -3)가 먼저 배치되고 그 뒤에 양수(4, 2, 6, 0)가 배치되는 것을 확인할 수 있습니다. 완전한 정렬이 필요하다면 sort() 함수를, 음수와 양수의 그룹 분리만 필요하다면 재귀 방식을 선택하는 것이 좋습니다.