문제 개요
[시작, 끝] 형태의 구간 리스트가 주어진다고 가정해 보겠습니다. 각 구간은 걸고 싶은 배너의 시작 지점과 끝 지점을 나타냅니다. 배너를 걸기 위해서는 최소 한 개의 핀이 필요하며, 하나의 핀으로 여러 개의 배너를 동시에 걸 수도 있습니다. 이때 구해야 할 것은 모든 배너를 걸기 위해 필요한 최소 핀 개수입니다.
예를 들어 입력이 [[2, 5], [5, 6], [8, 10], [10, 13]]이라면 결과는 2입니다. 위치 5와 위치 10에 두 개의 핀을 두면 네 개의 배너를 모두 걸 수 있기 때문입니다.
접근 방법
이 문제는 대표적인 그리디(Greedy) 알고리즘 문제로, 다음 단계를 따르면 해결할 수 있습니다.
- 구간 배열 v를 각 구간의 끝 값(end)을 기준으로 오름차순 정렬합니다.
- 결과 변수 ret := 0으로 초기화합니다.
- 마지막 핀 위치 last := -inf(매우 작은 값)로 초기화합니다.
- v의 각 구간 it에 대해 다음을 반복합니다.
- last가 현재 구간의 시작 값보다 크거나 같다면, 이미 놓인 핀이 이 배너도 함께 걸 수 있으므로 건너뜁니다.
- 그렇지 않으면 새 핀이 필요하므로 ret을 1 증가시킵니다.
- last를 현재 구간의 끝 값으로 갱신합니다.
- 모든 반복이 끝나면 ret을 반환합니다.
구간을 끝 값 기준으로 정렬하는 이유는, 핀을 가능한 한 구간의 오른쪽 끝에 두어 이후 등장하는 구간들을 최대한 많이 커버할 수 있기 때문입니다. 이렇게 하면 하나의 핀이 최대한 많은 배너를 담당하게 되어 전체 핀 개수가 자연스럽게 최소화됩니다.
예제 코드 (C++)
아래 구현을 살펴보면 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a.back() < b.back();
}
int solve(vector<vector<int>>& v) {
sort(v.begin(), v.end(), cmp);
int ret = 0;
int last = -1e8;
for (auto& it : v) {
if (last >= it[0]) {
continue;
}
ret++;
last = it[1];
}
return ret;
}
};
int solve(vector<vector<int>>& intervals) {
return (new Solution())->solve(intervals);
}
int main(){
vector<vector<int>> v = {{2, 5},{5, 6},{8, 10},{10, 13}};
cout << solve(v);
}
입력
{{2, 5},{5, 6},{8, 10},{10, 13}}
출력
2
시간 복잡도
정렬에 O(n log n), 구간 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 추가 배열 없이 처리하므로 O(1) 수준입니다.