문제 개요
N개의 요소를 가진 배열 arr[]와 정수 K(K < N)가 주어졌을 때, 동일한 배열에 K개의 정수 요소를 삽입하여 결과 배열의 중앙값(median)을 최대화하는 것이 목표입니다.
예를 들어, 입력 배열이 {1, 3, 2, 5}이고 k = 3이라면 다음과 같이 진행됩니다.
- 배열을 정렬하면 {1, 2, 3, 5}가 됩니다.
- 최댓값인 5보다 큰 3개의 요소(예: 6, 6, 6)를 삽입합니다. 그러면 배열은 {1, 2, 3, 5, 6, 6, 6}이 됩니다.
- 새 배열의 중앙값은 5입니다.
접근 방법
중앙값을 최대화하는 핵심 아이디어는 매우 간단합니다.
- 결과 배열의 중앙값을 최대화하려면, 삽입하는 모든 요소가 반드시 기존 배열의 최댓값보다 커야 합니다. 이렇게 하면 새로운 요소들이 항상 배열의 뒤쪽 절반에 위치하게 되어 중앙값이 밀려 올라갑니다.
- 배열을 오름차순으로 정렬한 후, 전체 크기(n + k)가 홀수이면 중앙값은 arr[size / 2]이고, 짝수이면 (arr[(size / 2) - 1] + arr[size / 2]) / 2가 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
double getMaxMedian(int *arr, int n, int k){
int newSize = n + k;
double median;
sort(arr, arr + n);
if (newSize % 2 == 0) {
median = (arr[(newSize / 2) - 1] + arr[newSize / 2]) / 2;
return median;
}
median = arr[newSize / 2];
return median;
}
int main(){
int arr[] = {1, 3, 2, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Max median = " << getMaxMedian(arr, n, k) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.
Max median = 5
정리
이 문제의 시간 복잡도는 정렬 단계가 지배적이므로 O(N log N)입니다. 핵심은 삽입할 값들을 최댓값보다 크게 만드는 것만으로도 중앙값이 자동으로 최대화된다는 점입니다. 실제로 어떤 구체적인 값을 넣을지는 중요하지 않으며, 기존 최댓값보다 크기만 하면 됩니다.