C++로 배열의 중앙값을 x와 같게 만들기 위해 추가해야 하는 최소 요소 개수 구하기

문제 개요

크기가 n인 배열 "arr"와 값 x가 주어졌을 때, 배열에 최소 몇 개의 요소를 추가해야 중앙값(median)이 x와 같아지는지 구하는 것이 이 문제의 목표입니다.

여기서 중앙값이란 배열의 요소들을 비내림차순(오름차순)으로 정렬했을 때 (n-1)/2번째 위치에 있는 요소를 의미합니다. 예를 들어 다음 배열의 중앙값은 20입니다.

arr1[] = {10, 20, 30, 40}

만약 arr[] = {1, 2, 3}이고 x = 4라고 가정해 보겠습니다. 이 경우 배열에 4개의 요소({4, 4, 4, 4})를 추가하여 {1, 2, 3, 4, 4, 4, 4}로 만들면 중앙값이 4가 되므로, 정답은 4입니다.

알고리즘

접근 방식은 매우 간단합니다. 배열의 중앙값이 x와 같아질 때까지 x를 하나씩 계속 추가하면 됩니다. 구체적인 단계는 다음과 같습니다.

1. 배열을 먼저 정렬합니다.
2. 현재 중앙값(arr[(n-1)/2])이 x와 같은지 확인합니다.
3. 같지 않다면 배열 끝에 x를 추가하고, 배열 크기를 1 늘린 뒤 다시 정렬합니다.
4. 추가한 횟수(cnt)를 1 증가시키고 2~3단계를 반복합니다.
5. 중앙값이 x와 같아지면 반복을 종료하고 추가한 횟수를 반환합니다.

예제 코드

#include <iostream>
#include <algorithm>
using namespace std;
int minNumbersToBeAdded(int *arr, int n, int x){
    sort(arr, arr + n);
    int cnt = 0;
    while (arr[(n - 1)/2] != x) {
        arr[n] = x;
        ++n;
        sort(arr, arr + n);
        ++cnt;
    }
    return cnt;
}
int main(){
    int arr[20] = {1, 2, 3};
    int x = 4;
    int n = 3;
    cout << "Minimum numbers to be added = " << minNumbersToBeAdded(arr, n, x) << endl;
    return 0;
}

출력 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Minimum numbers to be added = 4

코드 설명

minNumbersToBeAdded 함수는 먼저 sort 함수를 사용해 배열을 정렬한 뒤, while 루프 안에서 현재 중앙값이 x와 일치하는지 검사합니다. 일치하지 않으면 배열의 다음 빈 공간(arr[n])에 x를 저장하고 배열 크기 n을 증가시킨 후 다시 정렬합니다. 이 과정에서 추가 횟수 cnt가 매번 1씩 증가하며, 중앙값이 x가 되는 순간 루프가 종료되고 cnt가 반환됩니다.

위 예제에서 초기 배열 {1, 2, 3}의 중앙값은 2입니다. x = 4를 한 번씩 추가할 때마다 배열이 {1, 2, 3, 4}, {1, 2, 3, 4, 4}, {1, 2, 3, 4, 4, 4}, {1, 2, 3, 4, 4, 4, 4}로 변화하며, 마지막 배열의 중앙값은 4가 됩니다. 따라서 총 4개의 요소를 추가해야 한다는 결과가 출력됩니다.