문제 개요
짝수와 홀수 값이 섞여 있는 정수 배열이 주어졌을 때, 다음 조건을 만족하도록 배열을 재정렬하는 것이 과제입니다.
- 인덱스 i가 짝수이면 arr[i]는 그 앞의 모든 요소 arr[j](j < i)보다 크거나 같아야 합니다.
- 인덱스 i가 홀수이면 arr[i]는 그 앞의 모든 요소 arr[j](j < i)보다 작거나 같아야 합니다.
쉽게 말해, 짝수 번째 자리(0, 2, 4, ...)에는 값이 점점 작아지고, 홀수 번째 자리(1, 3, 5, ...)에는 값이 점점 커지는 교차 패턴을 만들면 됩니다.
입출력 시나리오
입력 − int arr[] = {5, 9, 10, 12, 32, 35, 67, 89}
출력 − 재정렬 후 배열: 12 32 10 35 9 67 5 89
설명 − 배열을 오름차순으로 정렬하면 {5, 9, 10, 12, 32, 35, 67, 89}가 됩니다. 여기서 작은 쪽 절반(5, 9, 10, 12)은 짝수 인덱스에 내림차순으로 배치되고, 큰 쪽 절반(32, 35, 67, 89)은 홀수 인덱스에 오름차순으로 배치됩니다. 그 결과 어느 위치에서든 위 조건이 성립합니다.
입력 − int arr[] = {4, 5, 1, 2, 9, 10}
출력 − 재정렬 후 배열: 4 5 2 9 1 10
설명 − 같은 방식으로 정렬된 배열의 앞부분 값들은 짝수 인덱스에, 뒷부분 값들은 홀수 인덱스에 배치하여 조건을 충족시킵니다.
알고리즘 접근 방식
핵심 아이디어는 배열을 먼저 정렬한 뒤, 작은 값들과 큰 값들을 규칙적으로 교차 배치하는 것입니다. 프로그램의 동작 단계는 다음과 같습니다.
- 정수형 배열을 선언하고 size = sizeof(arr) / sizeof(arr[0]) 공식으로 배열의 크기를 계산합니다.
- array_rearrange(arr, size) 함수를 호출해 배열과 크기를 매개변수로 전달합니다.
- 변수 even을 size / 2로 설정하고, 변수 odd를 size - even으로 설정합니다.
- 변수 temp를 odd - 1로 초기화하고, 원본 배열과 같은 크기의 보조 배열 arr_2[]를 준비합니다.
- for 반복문으로 원본 배열의 모든 요소를 arr_2[]에 복사합니다.
- sort(arr_2, arr_2 + size)를 호출해 보조 배열을 오름차순으로 정렬합니다.
- 인덱스 0부터 2씩 건너뛰며(짝수 인덱스) arr[i]에 arr_2[temp]를 대입하고 temp를 1씩 감소시킵니다. 이렇게 하면 정렬된 배열의 작은 값들이 짝수 위치에 내림차순으로 채워집니다.
- temp를 odd로 되돌린 뒤, 인덱스 1부터 2씩 건너뛰며(홀수 인덱스) arr[i]에 arr_2[temp]를 대입하고 temp를 1씩 증가시킵니다. 이렇게 하면 큰 값들이 홀수 위치에 오름차순으로 채워집니다.
- 마지막으로 배열 전체를 순회하며 재정렬된 결과를 출력합니다.
예제
#include <bits/stdc++.h>
using namespace std;
void array_rearrange(int arr[], int size){
int even = size / 2;
int odd = size - even;
int temp = odd - 1;
int arr_2[size];
for(int i = 0; i < size; i++){
arr_2[i] = arr[i];
}
sort(arr_2, arr_2 + size);
for(int i = 0; i < size; i += 2){
arr[i] = arr_2[temp];
temp--;
}
temp = odd;
for(int i = 1; i < size; i += 2){
arr[i] = arr_2[temp];
temp++;
}
cout<<"Array after rearranging elements are: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
}
int main(){
int arr[] = {5, 9, 10, 12, 32, 35, 67, 89};
int size = sizeof(arr) / sizeof(arr[0]);
array_rearrange(arr, size);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 생성됩니다.
Array after rearranging elements are: 12 32 10 35 9 67 5 89
동작 원리 검증
예제 입력으로 결과가 어떻게 만들어지는지 단계별로 확인해 보겠습니다.
- 정렬된 배열: {5, 9, 10, 12, 32, 35, 67, 89}, even = 4, odd = 4, temp = 3
- 짝수 인덱스 채우기: arr[0] = 12, arr[2] = 10, arr[4] = 9, arr[6] = 5
- 홀수 인덱스 채우기: arr[1] = 32, arr[3] = 35, arr[5] = 67, arr[7] = 89
짝수 인덱스의 값은 왼쪽으로 갈수록 커지므로 임의의 짝수 i에 대해 arr[i] ≥ arr[j](j < i)가 항상 성립하고, 홀수 인덱스의 값은 왼쪽으로 갈수록 작아지므로 arr[i] ≤ arr[j](j < i)가 항상 성립합니다.
복잡도 분석
- 시간 복잡도: 정렬에 O(n log n), 배치에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다.
- 공간 복잡도: 크기 n의 보조 배열을 사용하므로 O(n)입니다.