문제 개요
양의 정수로 이루어진 배열 arr[]가 주어졌을 때, 홀수 인덱스에 위치한 모든 요소가 바로 앞의 요소(짝수 인덱스)보다 크도록 배열을 재정렬하고 그 결과를 출력하는 것이 이 글의 목표입니다.
입출력 예제
입력 − int arr[] = {2, 1, 5, 4, 3, 7, 8}
출력 −
정렬 전 배열: 2 1 5 4 3 7 8
모든 홀수 인덱스 요소가 이전 요소보다 크도록 재정렬한 배열: 1 4 2 5 3 8 7
설명 − 크기가 7인 정수 배열이 주어졌습니다. 짝수 인덱스의 요소가 홀수 인덱스의 요소보다 크면 두 요소의 위치를 교환(swap)합니다.
Arr[0] > arr[1] → swap 호출 = {1, 2, 5, 4, 3, 7, 8}
Arr[2] > arr[3] → swap 호출 = {1, 2, 4, 5, 3, 7, 8}
Arr[6] > arr[5] → swap 호출 = {1, 2, 4, 5, 3, 8, 7}
Arr[2] > arr[1] → swap 호출 = {1, 4, 2, 5, 3, 8, 7}입력 − int arr[] = {3, 2, 6, 9}
출력 −
정렬 전 배열: 3 2 6 9
모든 홀수 인덱스 요소가 이전 요소보다 크도록 재정렬한 배열: 2 3 6 9
설명 − 크기가 4인 정수 배열이 주어졌습니다. Arr[0] > arr[1]이므로 swap을 호출하여 {2, 3, 6, 9}가 됩니다. 이후 모든 위치의 요소가 조건을 만족하므로 추가적인 swap은 필요하지 않습니다.
알고리즘 접근 방법
- 정수형 요소로 이루어진 배열을 입력받고 배열의 크기를 계산합니다.
- 정렬 전 배열을 출력한 뒤 Rearrangement(arr, size) 함수를 호출합니다.
- Rearrangement(arr, size) 함수 내부에서는 다음을 수행합니다.
- 정수형 변수 ptr을 선언하고 size-1로 초기화합니다.
- i를 0부터 ptr 미만까지 2씩 증가시키며 반복합니다. 반복문 안에서 arr[i]가 arr[i+1]보다 크면 swap(arr[i], arr[i+1])을 호출합니다.
- size가 홀수인지 확인(size & 1)하고, 홀수라면 i를 ptr부터 0보다 클 때까지 2씩 감소시키며 반복합니다. 반복문 안에서 arr[i]가 arr[i-1]보다 크면 swap(arr[i], arr[i-1])을 호출합니다.
- 재정렬이 완료된 배열을 출력합니다.
예제 코드
#include <iostream>
using namespace std;
void Rearrangement(int arr[], int size){
int ptr = size - 1;
for(int i = 0; i < ptr; i = i+2){
if(arr[i] > arr[i+1]){
swap(arr[i], arr[i+1]);
}
}
if(size & 1){
for(int i = ptr; i > 0; i = i-2){
if(arr[i] > arr[i-1]){
swap(arr[i], arr[i-1]);
}
}
}
}
int main(){
//배열 입력
int arr[] = {2, 1, 5, 4, 3, 7, 8};
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<<" Rearrangement of an array such that every odd indexed element is greater than it previous is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Array before Arrangement: 2 1 5 4 3 7 8
Rearrangement of an array such that every odd indexed element is greater than it previous is: 1 4 2 5 3 8 7
복잡도 분석
이 알고리즘은 배열을 최대 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가적인 공간 없이 제자리(in-place)에서 수행되므로 공간 복잡도는 O(1)입니다.
마무리
인접한 요소들을 조건에 맞게 교환하는 간단한 방식만으로도 홀수 인덱스의 요소가 항상 이전 요소보다 크도록 배열을 재정렬할 수 있습니다. 특히 배열의 길이가 홀수인 경우 마지막 인덱스부터 역방향으로 한 번 더 검사를 수행하는 것이 이 알고리즘의 핵심 포인트입니다.