C++로 배열의 중앙값 최대화하기

문제 정의

N개의 요소를 가진 배열 arr[]와 정수 K(K < N)가 주어졌을 때, 동일한 배열에 K개의 정수 요소를 삽입하여 결과 배열의 중앙값(median)을 최대화하는 것이 목표입니다.

예를 들어, 입력 배열이 {1, 3, 2, 5}이고 k = 3이라면 다음과 같이 진행됩니다.

• 배열을 정렬하면 {1, 2, 3, 5}가 됩니다.
• 최댓값인 5보다 큰 정수 3개(예: 6)를 삽입합니다. 이 연산 후 배열은 {1, 2, 3, 5, 6, 6, 6}이 됩니다.
• 새 배열의 중앙값은 5입니다.

접근 방법 및 알고리즘

결과 배열의 중앙값을 최대화하기 위해서는 삽입하는 모든 요소가 반드시 기존 배열의 최댓값보다 커야 합니다. 그래야 새로 삽입된 요소들이 중앙 위치 뒤쪽에 배치되어 기존 요소들의 중앙값이 유지되거나 향상되기 때문입니다.

구체적인 알고리즘은 다음과 같습니다.

1. 삽입할 모든 요소는 배열의 최댓값보다 큰 값으로 선택합니다.
2. 배열을 정렬한 후, 전체 크기(n + k)가 홀수이면 중앙값은 arr[크기 / 2]이고, 짝수이면 (arr[(크기 / 2) - 1] + arr[크기 / 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)입니다. 여기서 N은 원래 배열의 크기입니다. 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다.