C++로 해결하는 포함된 구간(Contained Intervals) 문제 – 정렬과 그리디 기법 활용하기

문제 개요

각 구간(interval)이 [시작, 끝]의 두 값으로 표현되는 2차원 구간 리스트가 주어집니다. 이때 한 구간이 다른 구간을 완전히 포함하는 경우가 하나라도 존재하는지 판별해야 합니다.

예를 들어 입력이 [[2,4],[5,11],[5,9],[10,10]]라고 한다면, [5,11]이 [5,9]를 포함하고 있기 때문에 결과는 true(1)가 됩니다.

해결 접근 방식

이 문제는 정렬과 그리디(greedy) 탐색을 결합하면 O(n log n) 시간 복잡도 안에서 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

1. 구간 정렬: 구간 배열 v를 사용자 정의 비교 함수로 정렬합니다. 끝점(end)이 작은 구간이 앞에 오고, 끝점이 같다면 시작점(start)이 큰 구간이 먼저 오도록 합니다.
2. 결과 배열 준비: 이미 처리한 구간을 저장할 2차원 배열 ret을 선언합니다.
3. 순회 및 판별: 정렬된 각 구간 it에 대해 아래 조건을 검사합니다.
   • ret이 비어 있다면 현재 구간을 ret의 끝에 추가합니다.
   • 그렇지 않고 ret의 마지막 구간 시작점이 현재 구간의 시작점보다 크거나 같다면, 현재 구간이 이전 구간을 포함하는 것이므로 true를 즉시 반환합니다.
   • 그 외의 경우에는 현재 구간을 ret의 끝에 추가합니다.
4. 모든 구간을 검사한 후에도 포함 관계를 찾지 못했다면 false를 반환합니다.

동작 원리: 끝점 기준 오름차순 정렬 덕분에 ret의 마지막 구간은 항상 현재 구간보다 끝점이 작거나 같습니다. 따라서 마지막 구간의 시작점이 현재 구간의 시작점 이상이라면, 현재 구간이 해당 구간을 완전히 감싸고 있는 것이므로 바로 true를 반환할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool static cmp(vector<int> &a, vector<int> &b) {
        return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
    }
    bool solve(vector<vector<int>> &v) {
        sort(v.begin(), v.end(), cmp);
        vector<vector<int>> ret;
        for (auto &it : v) {
            if (ret.empty())
            ret.push_back(it);
            else if (ret.back()[0] >= it[0])
            return true;
            else
            ret.push_back(it);
        }
        return false;
    }
};
main() {
    Solution ob;
    vector<vector<int>> v = {{2,4},{5,11},{5,9},{10,10}};
    cout << (ob.solve(v));
}

입력

{{2,4},{5,11},{5,9},{10,10}}

출력

1

복잡도 분석

정렬에 O(n log n), 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 추가 공간은 최대 n개의 구간을 저장하는 ret 배열로 인해 O(n)이 필요합니다.