C++로 정확히 K개의 원소를 삭제한 후 배열에서 얻을 수 있는 최대 중간값 구하기

이 튜토리얼에서는 배열에서 정확히 K개의 원소를 삭제한 후 남은 배열의 중간 원소가 가질 수 있는 최댓값을 구하는 방법을 다룹니다.

문제의 조건은 다음과 같습니다. 크기가 N인 배열과 정수 K가 주어지며, 우리는 배열에서 K개의 원소를 제거하여 결과 배열의 중간 원소가 최대한 커지도록 만들어야 합니다.

접근 방법

K개의 원소를 삭제하면 남는 배열의 크기는 n - k가 됩니다. 이때 중간 원소의 위치(1-based 인덱스)는 (n - k + 1) / 2입니다.

핵심 아이디어는 삭제되는 K개의 원소를 어느 쪽에 배치할지 자유롭게 선택할 수 있다는 점입니다. 즉, 최종 중간 원소는 원래 배열에서 (n - k + 1) / 2번째 위치부터 최대 K칸 오른쪽인 (n - k + 1) / 2 + k번째 위치 사이의 어떤 원소도 될 수 있습니다.

따라서 이 범위 내의 원소들 중 최댓값을 찾으면 그것이 곧 가능한 중간 원소의 최댓값이 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 중간 원소의 최댓값 계산
int maximum_middle_value(int n, int k, int arr[]) {
    int ans = -1;
    int low = (n + 1 - k) / 2;      // 중간 위치의 최솟값
    int high = (n + 1 - k) / 2 + k; // 중간 위치의 최댓값
    for (int i = low; i <= high; i++) {
        ans = max(ans, arr[i - 1]);
    }
    return ans;
}

int main() {
    int n = 5, k = 2;
    int arr[] = { 9, 5, 3, 7, 10 };
    cout << maximum_middle_value(n, k, arr) << endl;

    n = 9;
    k = 3;
    int arr1[] = { 2, 4, 3, 9, 5, 8, 7, 6, 10 };
    cout << maximum_middle_value(n, k, arr1) << endl;

    return 0;
}

실행 결과

7
9

동작 원리 설명

첫 번째 예제

N = 5, K = 2이고 배열은 {9, 5, 3, 7, 10}입니다. 삭제 후 남는 배열의 크기는 3이며, 중간 위치는 (5 - 2 + 1) / 2 = 2번째입니다. 탐색 범위는 2번째부터 4번째까지이므로 해당 원소들은 {5, 3, 7}이고, 이중 최댓값인 7이 답이 됩니다.

두 번째 예제

N = 9, K = 3이고 배열은 {2, 4, 3, 9, 5, 8, 7, 6, 10}입니다. 삭제 후 남는 배열의 크기는 6이며, 중간 위치는 (9 - 3 + 1) / 2 = 3번째입니다. 탐색 범위는 3번째부터 6번째까지이므로 해당 원소들은 {3, 9, 5, 8}이고, 이중 최댓값인 9가 답이 됩니다.

시간 복잡도

탐색 범위의 크기가 최대 K + 1이므로 시간 복잡도는 O(K)이며, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 배열을 정렬할 필요가 없기 때문에 매우 효율적인 해결 방법입니다.