양수와 음수를 모두 포함하는 정수형 배열 arr[]가 주어졌을 때, 짝수 위치에 있는 모든 요소가 홀수 위치에 있는 요소보다 크도록 배열을 재정렬하고 그 결과를 출력하는 것이 이 글의 과제입니다.
여기서 말하는 '위치'는 1부터 시작하는 것으로 가정합니다. 즉, 첫 번째 요소(인덱스 0)는 홀수 위치, 두 번째 요소(인덱스 1)는 짝수 위치에 해당하므로, 결국 인덱스가 홀수인 자리의 값이 인덱스가 짝수인 자리의 값보다 항상 커야 합니다.
입출력 시나리오 살펴보기
입력 − int arr[] = {2, 1, 4, 3, 6, 5, 8, 7}
출력 −
정렬 전 배열: 2 1 4 3 6 5 8 7
짝수 위치가 홀수 위치보다 크도록 재정렬한 배열: 1 8 2 7 3 6 4 5
설명 − 양수와 음수를 포함한 크기 8의 정수 배열이 주어집니다. 배열을 오름차순으로 정렬한 뒤, 가장 작은 값은 홀수 위치에, 가장 큰 값은 짝수 위치에 교차하여 배치하면 1 8 2 7 3 6 4 5가 됩니다. 이 배열에서 짝수 위치의 값(8, 7, 6, 5)은 항상 바로 앞 홀수 위치의 값(1, 2, 3, 4)보다 큽니다.
입력 − int arr[] = {-3, 2, -4, -1}
출력 −
정렬 전 배열: -3 2 -4 -1
짝수 위치가 홀수 위치보다 크도록 재정렬한 배열: -4 2 -3 -1
설명 − 양수와 음수를 포함한 크기 4의 정수 배열이 주어집니다. 같은 방식으로 재정렬하면 -4 2 -3 -1이 되며, 2번째 위치의 2는 1번째 위치의 -4보다 크고, 4번째 위치의 -1은 3번째 위치의 -3보다 큽니다.
프로그램에서 사용되는 접근 방식
정수형 요소로 이루어진 배열을 입력받고 배열의 크기를 계산합니다.
C++ STL의 sort() 함수에 배열의 시작 주소와 끝 주소를 전달하여 배열을 오름차순으로 정렬합니다.
Rearrangement(arr, size) 함수를 호출하여 배열을 재정렬합니다.
Rearrangement(arr, size) 함수 내부에서는 다음과 같이 동작합니다.
배열 arr[size]와 같은 크기의 정수형 배열 ptr[size]를 선언합니다.
임시 정수 변수 first를 0으로, last를 size - 1로 초기화합니다.
i를 0부터 배열 크기 미만까지 반복하는 for 루프를 실행합니다. 루프 안에서 (i + 1) % 2가 0이라면, 즉 현재 위치가 짝수 위치라면 ptr[i]에 정렬된 배열의 마지막 값(arr[last--])을 저장합니다.
그렇지 않은 경우(홀수 위치)에는 ptr[i]에 정렬된 배열의 처음 값(arr[first++])을 저장합니다.
완성된 ptr 배열을 원래 배열 arr에 복사한 뒤 결과를 출력합니다.
이 방식의 핵심은 정렬된 배열의 양쪽 끝에서 값을 하나씩 번갈아 가져오는 것입니다. 그러면 "작은 값, 큰 값, 그다음 작은 값, 그다음 큰 값..." 순서로 자연스럽게 배치되어 짝수 위치의 값이 항상 앞의 홀수 위치 값보다 크게 됩니다.
예제
#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int* arr, int size){
int ptr[size];
int first = 0;
int last = size - 1;
for (int i = 0; i < size; i++){
if((i + 1) % 2 == 0){
ptr[i] = arr[last--];
}
else{
ptr[i] = arr[first++];
}
}
//재정렬된 값을 원래 배열로 복사
for (int i = 0; i < size; i++){
arr[i] = ptr[i];
}
}
int main(){
//배열 입력
int arr[] = {2, 1, 4, 3, 6, 5, 8, 7};
int size = sizeof(arr) / sizeof(arr[0]);
//원본 배열 출력
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//배열 정렬
sort(arr, arr + size);
//배열 재정렬 함수 호출
Rearrangement(arr, size);
//재정렬 후 배열 출력
cout<<"\nRearrangement of an array such that even positioned are greater than odd is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Array before Arrangement: 2 1 4 3 6 5 8 7
Rearrangement of an array such that even positioned are greater than odd is: 1 8 2 7 3 6 4 5
복잡도 분석
시간 복잡도: 배열 정렬에 O(n log n), 재정렬에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다.
공간 복잡도: 보조 배열 ptr[]를 사용하므로 O(n)입니다.