정수형 배열에는 양수와 음수가 섞여 있을 수 있습니다. 이번 글에서는 추가 메모리를 O(1), 즉 상수 크기만 사용하면서 배열 안의 양수와 음수가 서로 번갈아 나오도록 재정렬하는 방법을 C++ 코드로 살펴보겠습니다.
목표는 다음과 같습니다. 양수 바로 뒤에는 음수가, 음수 바로 뒤에는 양수가 오도록 교대 배치를 만드는 것입니다. 만약 한쪽 부호의 원소가 더 많다면, 남은 원소들은 배열의 끝에 그대로 붙이게 됩니다.
입력·출력 예시로 이해하기
먼저 몇 가지 시나리오를 통해 문제를 구체적으로 확인해 보겠습니다.
입력 1: int arr[] = {-1, -2, -3, 1, 2, 3}
출력 1:
정렬 전 배열: -1 -2 -3 1 2 3 O(1) 추가 공간으로 양수·음수 번갈아 재정렬한 결과: -1 1 -2 2 -3 3
설명: 크기가 6인 정수 배열이 주어졌습니다. 양수와 음수 개수가 같으므로 모든 원소가 교대로 배치되며, 최종 결과는 -1 1 -2 2 -3 3이 됩니다.
입력 2: int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}
출력 2:
정렬 전 배열: -1 -2 -3 1 2 3 5 5 -5 3 1 1 O(1) 추가 공간으로 양수·음수 번갈아 재정렬한 결과: -1 1 -2 2 -3 3 -5 5 5 3 1 1
설명: 크기가 12인 배열입니다. 교대 배치가 가능한 범위까지만 재정렬이 진행되고, 남는 양수들(5 5 3 1 1)은 배열 끝에 그대로 위치하게 됩니다.
알고리즘 접근 방법
이 프로그램은 제자리(in-place) 방식으로 동작하며, 핵심 아이디어는 다음과 같습니다.
- 정수형 배열을 입력받고 배열의 크기를 계산합니다.
- FOR 반복문을 사용해 재정렬 전의 배열 상태를 먼저 출력합니다.
- 배열과 크기를 인자로 전달하며 Rearrangement(arr, size) 함수를 호출합니다.
- Rearrangement(arr, size) 함수 내부에서는 다음 작업이 수행됩니다.
- 정수 변수 ptr을 선언하고 -1로 초기화합니다. ptr은 "교체가 필요한 자리"를 가리키는 포인터 역할을 합니다.
- i를 0부터 size 미만까지 반복합니다. 반복 중 ptr이 0 이상이라면, arr[i]와 arr[ptr]의 부호가 서로 다른지 검사합니다. 부호가 다르면 move_array(arr, size, ptr, i)를 호출해 원소를 옮기고, i - ptr이 2 이상이면 ptr을 2 증가시켜 다음 교체 자리를 준비합니다. 그렇지 않으면 ptr을 다시 -1로 설정합니다.
- ptr이 -1인 경우에는 현재 인덱스 i의 짝수·홀수 여부와 arr[i]의 부호를 비교합니다. 짝수 인덱스에 양수가 있거나 홀수 인덱스에 음수가 있는 등 "자리가 어긋난" 경우 해당 인덱스를 ptr로 저장해 이후 교체 대상으로 표시합니다.
- move_array(int arr[], int size, int ptr, int temp) 함수 내부에서는 다음 작업이 수행됩니다.
- arr[temp] 값을 임시 변수 ch에 저장합니다.
- i를 temp부터 ptr보다 클 때까지 감소시키며, arr[i]에 arr[i - 1]을 대입해 원소들을 한 칸씩 뒤로 밀어냅니다.
- 마지막으로 arr[ptr]에 ch를 대입해 원소를 목표 위치에 삽입합니다.
이 방식은 별도의 보조 배열 없이 기존 배열 안에서 원소를 이동시키므로 추가 공간 복잡도가 O(1)입니다. 다만 원소를 한 칸씩 밀어내는 연산 때문에 최악의 경우 시간 복잡도는 O(n²)이 될 수 있습니다.
C++ 구현 예제
#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
char ch = arr[temp];
for(int i = temp; i > ptr; i--){
arr[i] = arr[i - 1];
}
arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
int ptr = -1;
for(int i = 0; i < size; i++){
if (ptr >= 0){
if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
move_array(arr, size, ptr, i);
if(i - ptr >= 2){
ptr = ptr + 2;
}
else{
ptr = -1;
}
}
}
if(ptr == -1){
if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
ptr = i;
}
}
}
}
int main(){
// 입력 배열
int arr[] = {-1, -2, -3, 1, 2, 3};
int size = sizeof(arr) / sizeof(arr[0]);
// 원본 배열 출력
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
// 배열 재정렬 함수 호출
Rearrangement(arr, size);
// 재정렬 후 배열 출력
cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Array before Arrangement: -1 -2 -3 1 2 3 Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3
마무리
이처럼 포인터 하나(ptr)만 활용해 잘못된 위치에 있는 원소를 찾아내고, move_array 함수로 원소를 밀어내며 삽입하는 방식이면 추가 배열 없이도 양수와 음수를 교대로 배치할 수 있습니다. 메모리 사용량이 중요한 임베디드 환경이나 면접에서 자주 등장하는 유형이니, 원리를 잘 기억해 두면 유용하게 활용할 수 있습니다.