정수형 배열이 주어졌을 때, 이 배열은 정렬되어 있을 수도 있고 그렇지 않을 수도 있습니다. 우리의 과제는 먼저 값들이 정렬되어 있지 않다면 배열을 정렬한 뒤, 배열의 첫 번째 요소는 최댓값, 두 번째 요소는 최솟값, 세 번째 요소는 두 번째로 큰 값, 네 번째 요소는 두 번째로 작은 값으로 배치하는 식으로 재배열하는 것입니다.
입력 및 출력 시나리오 예시
Input − int arr[] = {7, 5, 2, 3, 4, 9, 10, 5}
Output − 정렬 후 배열: 2 3 4 5 5 7 9 10
최대-최소 형태로 재배열된 배열: 10 2 9 3 7 4 5 5
설명 − {7, 5, 2, 3, 4, 9, 10, 5} 값을 가진 정수형 배열이 주어집니다. 먼저 배열을 정렬하면 {2, 3, 4, 5, 5, 7, 9, 10}이 됩니다. 그다음 가장 큰 원소인 10을 arr[0]에, 가장 작은 원소인 2를 arr[1]에, 두 번째로 큰 원소인 9를 arr[2]에 배치하는 방식으로 진행합니다. 최종 결과 배열은 10 2 9 3 7 4 5 5가 됩니다.
Input − int arr[] = {2, 4, 1, 6, 7}
Output − 정렬 후 배열: 1, 2, 4, 6, 7
최대-최소 형태로 재배열된 배열: 7, 1, 6, 2, 4
설명 − {2, 4, 1, 6, 7} 값을 가진 정수형 배열이 주어집니다. 먼저 배열을 정렬하면 {1, 2, 4, 6, 7}이 됩니다. 그다음 가장 큰 원소인 7을 arr[0]에, 가장 작은 원소인 1을 arr[1]에, 두 번째로 큰 원소인 6을 arr[2]에 배치합니다. 최종 결과 배열은 7, 1, 6, 2, 4가 됩니다.
프로그램에 적용된 접근 방식
정수형 배열을 입력받아 배열의 크기를 계산합니다. C++ STL의 sort 메서드에 arr[]와 배열의 크기를 인자로 전달하여 호출합니다.
정렬된 배열을 출력한 뒤, Rearr_Max_Min(arr, size) 함수를 호출합니다.
Rearr_Max_Min(arr, size) 함수 내부에서는 다음과 같이 동작합니다.
변수 max를 선언하고 size - 1로 초기화하며, 변수 min을 선언하고 0으로 초기화합니다. 또한 변수 max_val을 선언하여 arr[size - 1] + 1로 설정합니다.
i가 0부터 size보다 작을 때까지 FOR 반복문을 실행합니다. 반복문 안에서 i % 2 == 0인 경우 arr[i] = arr[i] + (arr[max] % max_val) * max_val로 설정하고 max를 1 감소시킵니다.
그렇지 않은 경우(홀수 인덱스), arr[i] = arr[i] + (arr[min] % max_val) * max_val로 설정하고 min을 1 증가시킵니다.
마지막으로 i가 0부터 size보다 작을 때까지 반복문을 실행하며 arr[i] = arr[i] / max_val 연산을 수행하여 원래 값만 남깁니다.
이 알고리즘의 핵심은 추가 배열 없이 O(1)의 추가 메모리만 사용한다는 점입니다. max_val은 정렬된 배열에서 나타날 수 있는 값보다 항상 크기 때문에, 기존 값에 max_val을 곱한 새로운 값을 더해두었다가 마지막에 max_val로 나누어 원하는 값만 추출할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void Rearr_Max_Min(int arr[], int size){
int max = size - 1;
int min = 0;
int max_val = arr[size - 1] + 1;
for (int i = 0; i < size; i++){
if (i % 2 == 0){
arr[i] += (arr[max] % max_val) * max_val;
max--;
}
else{
arr[i] += (arr[min] % max_val) * max_val;
min++;
}
}
for(int i = 0; i < size; i++){
arr[i] = arr[i] / max_val;
}
}
int main(){
// 입력 배열
int arr[] = {7, 5, 2, 3, 4, 9, 10, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
// 배열 정렬
sort(arr, arr + size);
// 정렬 후 원본 배열 출력
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
// 배열 재배열 함수 호출
Rearr_Max_Min(arr, size);
// 재배열 후 배열 출력
cout<<"\nRearrangement of an array in maximum minimum form is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Array before Arrangement: 2 3 4 5 5 7 9 10 Rearrangement of an array in maximum minimum form is: 10 2 9 3 7 4 5 5