C++로 Amax - Amin ≤ K를 만족하도록 배열에서 제거해야 하는 최소 원소 개수 구하기

문제 개요

N개의 정수와 값 K가 주어졌을 때, 남은 원소들의 최댓값과 최솟값의 차이가 Amax - Amin ≤ K 조건을 만족하도록 하기 위해 제거해야 하는 원소의 최소 개수를 구하는 문제입니다. 원소를 제거한 후에는 남아 있는 원소들 사이에서 Amax(최댓값)와 Amin(최솟값)이 다시 계산됩니다.

예시

배열 arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20}이고 k = 4라고 가정해 보겠습니다. 이 경우 정답은 5입니다.

배열 앞부분에서 1, 3, 4를 제거합니다.
배열 뒷부분에서 17과 20을 제거합니다.
최종 배열은 {9, 10, 11, 12}가 되며, 12 - 9 = 3 ≤ 4 조건을 만족합니다.

알고리즘 접근 방식

주어진 원소들을 먼저 오름차순으로 정렬합니다.
그리디(Greedy) 관점에서 보면, 조건을 만족할 때까지 최솟값 또는 최댓값 중 하나를 제거하는 것이 최선의 전략입니다. 제거 조합은 여러 가지가 있을 수 있으므로 모든 경우를 고려해야 합니다.
제거 방법은 두 가지뿐입니다. 최솟값을 제거하거나 최댓값을 제거하는 것입니다. 제거 후 남은 원소들의 인덱스 범위를 (i…j)라 하면, 초기 상태는 i = 0, j = n-1이고 제거된 원소 수는 0입니다.
a[j] - a[i] > k인 경우에만 원소를 제거하며, 두 가지 선택지는 (i+1…j) 또는 (i…j-1)입니다. 두 결과 중 더 작은 값을 취합니다.

동일한 (i, j) 범위에 대한 계산이 반복되지 않도록 메모이제이션(Memoization)을 활용하면 효율성을 크게 높일 수 있습니다.

C++ 구현 예제

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

int dp[MAX][MAX];

int removeCombinations(int *arr, int i, int j, int k) {
    if (i >= j) {
        return 0;
    } else if ((arr[j] - arr[i]) <= k) {
        return 0;
    } else if (dp[i][j] != -1) {
        return dp[i][j];
    } else if ((arr[j] - arr[i]) > k) {
        dp[i][j] = 1 + min(removeCombinations(arr, i + 1, j, k),
                           removeCombinations(arr, i, j - 1, k));
    }
    return dp[i][j];
}

int removeNumbers(int *arr, int n, int k) {
    sort(arr, arr + n);
    memset(dp, -1, sizeof(dp));
    return n == 1 ? 0 : removeCombinations(arr, 0, n - 1, k);
}

int main() {
    int arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
    cout << "Minimum numbers to be removed = "
         << removeNumbers(arr, n, k) << endl;
    return 0;
}

실행 결과

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

Minimum numbers to be removed = 5

정리

이 문제는 정렬 후 재귀와 메모이제이션을 결합한 동적 계획법(DP)으로 해결할 수 있습니다. 각 단계에서 최솟값을 제거하는 경우와 최댓값을 제거하는 경우를 모두 탐색하고, 그중 더 적은 제거 횟수를 선택함으로써 최적해를 보장할 수 있습니다. 시간 복잡도는 O(n²)이며, n이 큰 문제에서는 슬라이딩 윈도우 기법으로 O(n log n)까지 최적화할 수 있습니다.