숫자로 이루어진 배열 Arr1[]과 길이가 같거나 다른 또 다른 배열 Arr2[]가 주어집니다. Arr1[]은 오름차순으로 정렬되어 있지만 단 하나의 요소만 제자리에 있지 않습니다. 우리는 Arr2[]에서 Arr1[]의 잘못 배치된 요소를 대체하여 전체 배열을 다시 정렬 상태로 만들 수 있는 값을 찾아야 하며, 후보가 여러 개라면 그중 가장 큰 값을 선택해야 합니다.
입력
Arr1[]= { 1,3,5,7,2,11 }, Arr2[]= { 4,8,7,10,9 }출력
Arr1을 정렬 상태로 만들 수 있는 최대 요소: 10
설명 − Arr2[]에서 Arr1[]을 정렬 상태로 만들 수 있는 숫자는 8, 9, 10입니다. 세 값 모두 7보다 크거나 같고 11보다 작거나 같기 때문입니다. 이 중에서는 10이 가장 큽니다.
결과적으로 새로운 Arr1[]은 { 1,3,5,7,10,11 }이 되어 완전히 정렬된 상태가 됩니다.
입력
Arr1[]= { 12,5,22,17 }, Arr2[]= { 4,8,7,10,9 }출력
적합한 요소가 없습니다.
설명 − Arr2[]에는 12보다 크거나 같고 22보다 작거나 같은 숫자가 존재하지 않습니다.
따라서 Arr1[]은 정렬 상태로 복원할 수 없습니다.
프로그램의 접근 방식
배열 arr1[]과 arr2[]에 숫자를 저장합니다. Arr1[]은 한 요소를 제외하고 오름차순으로 정렬되어 있습니다.
sortMax(int arr1[], int arr2[], int n1, int n2) 함수는 두 배열과 각 길이를 매개변수로 받아, arr2[]에서 arr1[]의 잘못된 요소를 대체해 정렬을 복원할 수 있는 최대값을 찾으면 arr1[]을 갱신합니다.
arr1[]에서 잘못 배치된 요소의 인덱스를 변수 wpos에 저장하며 초기값은 -1입니다.
maxx는 arr1[]의 잘못 배치된 요소를 대체해 정렬을 복원할 수 있는 arr2[] 요소들 중 최대값을 저장합니다.
먼저 arr1[]을 순회하며 arr[i] < arr[i-1]인 지점, 즉 어긋난 요소를 찾아 그 인덱스 i를 wpos에 저장합니다.
이후 arr2[]를 순회하며 arr1[wpos-1]과 arr1[wpos+1] 사이에 들어갈 수 있는 요소를 찾고, 해당 요소가 존재하면 maxx와 비교합니다.
더 큰 값이 있으면 maxx를 갱신합니다.
마지막으로 arr1[wpos]를 maxx로 대체합니다.
조건에 맞는 요소를 찾았다면 maxx를 반환하고, 찾지 못했다면 -1을 반환합니다.
적합한 요소가 없으면 안내 메시지를 출력합니다.
찾았다면 정렬이 복원된 arr1[]을 출력합니다.
예제 코드
// 배열을 정렬 상태로 복원하는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// arr1을 정렬 상태로 만드는 함수
int sortMax(int arr1[], int arr2[], int n1, int n2){
int wpos = -1; // 잘못 배치된 요소의 위치
int maxx = -1; // 대체 가능한 최대값
int i, j;
// 어긋난 요소의 위치 탐색
for(i = 1; i < n1; i++)
if(arr1[i] < arr1[i-1])
wpos = i;
// arr2에서 대체 가능한 최대값 탐색
for(j = 0; j < n2; j++){
if(arr2[j] >= arr1[wpos-1] && arr2[j] <= arr1[wpos+1])
if(arr2[j] >= maxx)
maxx = arr2[j];
}
if(maxx != -1)
arr1[wpos] = maxx;
return maxx;
}
int main(){
int arr1[] = { 1, 3, 7, 4, 10 };
int arr2[] = { 2, 1, 6, 8, 9 };
int len1 = sizeof(arr1) / sizeof(arr1[0]);
int len2 = sizeof(arr2) / sizeof(arr2[0]);
int res = sortMax(arr1, arr2, len1, len2);
if(res == -1)
cout << "교환 불가! 적합한 요소가 없습니다.";
else {
cout << "arr1[]을 정렬 상태로 만드는 arr2[]의 최대값: " << res;
cout << endl << "Arr1[]: ";
for(int i = 0; i < len1; i++)
cout << arr1[i] << " ";
cout << endl << "Arr2[]: ";
for(int i = 0; i < len2; i++)
cout << arr2[i] << " ";
}
}출력 결과
arr1[]을 정렬 상태로 만드는 arr2[]의 최대값: 9 Arr1[]: 1 3 7 9 10 Arr2[]: 2 1 6 8 9