C++에서 제거할 최적의 구간을 찾는 프로그램

서로 겹칠 수 있는 닫힌 구간(closed interval)들의 목록이 주어져 있다고 가정해 봅시다. 여기서 '구간 하나를 삭제한 후, 나머지 구간들을 모두 병합하고, 마지막으로 남은 구간의 개수를 센다'는 연산을 생각할 수 있습니다. 우리가 구해야 하는 값은 바로 이 삭제 과정에서 얻을 수 있는 남은 구간 개수의 최댓값입니다.

예를 들어 입력이 intervals = [[5, 8], [6, 7], [7, 10], [9, 11]]이라면 출력은 2입니다. 그 이유는 다음과 같습니다.

• [5, 8]을 삭제하면 병합 결과는 [6, 11]이 됩니다.

• [6, 7]을 삭제하면 병합 결과는 [5, 11]이 됩니다.

• [7, 10]을 삭제하면 병합 결과는 [5, 8], [9, 11]이 됩니다.

• [9, 11]을 삭제하면 병합 결과는 [5, 10]이 됩니다.

따라서 [7, 10]을 삭제했을 때 남는 구간이 가장 많으므로, 이것이 최적의 선택입니다.

문제 해결 접근 방식

이 문제는 각 구간을 삭제하는 경우를 하나씩 시도하면서, 나머지 구간을 병합했을 때 남는 구간의 개수를 계산하는 방식으로 해결할 수 있습니다. 동일한 상태가 반복해서 계산되는 낭비를 막기 위해 메모이제이션(memoization)을 함께 활용합니다.

구체적인 풀이 단계는 다음과 같습니다.

1. pair<int, int> 형태의 배열 memo를 선언합니다.

2. 2차원 배열 intervals, 인덱스 i, 현재 끝점 end를 인자로 받는 함수 countIntervals()를 정의합니다.

   • i가 intervals의 크기와 같으면 0을 반환합니다.

   • memo[i].first < end이면 음의 무한대(INT_MIN)를 반환합니다.

   • memo[i].first == end이면 memo[i].second를 반환합니다.

   • end < intervals[i][0]이면, 즉 현재 구간이 앞선 구간들과 겹치지 않으면 memo[i] = {min(end, memo[i].first), 1 + countIntervals(intervals, i + 1, intervals[i][1])}로 갱신한 뒤 memo[i].second를 반환합니다.

   • 그렇지 않은 경우(구간이 겹치는 경우)에는 memo[i] = {min(end, memo[i].first), countIntervals(intervals, i + 1, max(intervals[i][1], end))}로 갱신한 뒤 memo[i].second를 반환합니다.

3. 메인 로직(solve())에서는 다음을 수행합니다.

   • memo 배열의 크기를 intervals의 크기로 재설정합니다.

   • intervals 배열을 오름차순으로 정렬합니다.

   • count = 0, result = 0, end = -1로 초기화합니다.

   • 각 구간을 순회하면서 해당 구간을 삭제한다고 가정하고 result = max(result, count + countIntervals(intervals, i + 1, end))로 결과를 갱신합니다.

   • end < intervals[i][0]이면 count를 1 증가시키고, end = max(end, intervals[i][1])로 끝점을 갱신합니다.

   • 순회가 끝나면 result를 반환합니다.

아래 예시 구현을 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> memo;
int countIntervals(vector<vector<int>>& intervals, int i, int end) {
    if (i == intervals.size()) return 0;
    if (memo[i].first < end)
    return INT_MIN;
    if (memo[i].first == end)
    return memo[i].second;
    if (end < intervals[i][0]) {
        memo[i] = {min(end, memo[i].first), 1 +
        countIntervals(intervals, i + 1, intervals[i][1])};
        return memo[i].second;
    }
    memo[i] = {min(end, memo[i].first),
    countIntervals(intervals, i + 1, max(intervals[i][1],
    end))};
    return memo[i].second;
}
int solve(vector<vector<int>>& intervals) {
    memo.clear();
    memo.resize(intervals.size(), {INT_MAX, -1});
    sort(intervals.begin(), intervals.end());
    int count = 0, result = 0, end = -1;
    vector<int> temp;
    for (int i = 0; i < intervals.size(); i++) {
        result = max(result, count + countIntervals(intervals, i + 1,
        end));
        if (end < intervals[i][0])
            count++;
        end = max(end, intervals[i][1]);
    }
    return result;
}
int main(){
    vector<vector<int>> v = {{5, 8}, {6, 7}, {7, 10}, {9, 11}};
    cout<<solve(v);
}

입력

{{5, 8}, {6, 7}, {7, 10}, {9, 11}}

출력

2

복잡도 분석

구간 정렬에 O(N log N)이 소요되고, 메모이제이션된 재귀 호출은 시작 인덱스와 끝점 조합에 대해 최대 O(N²)개의 상태를 탐색하므로, 전체 시간 복잡도는 O(N²)입니다. 여기서 N은 구간의 개수입니다.