문제 개요
간격(intervals) 목록이 주어졌을 때, 목록 내 다른 간격에 완전히 포함되는(덮이는) 간격을 모두 제거해야 합니다. 여기서 간격 [a, b)는 c <= a 이고 b <= d 인 경우에만 간격 [c, d)에 의해 덮인 것으로 간주합니다.
모든 포함된 간격을 제거한 뒤에는 남아 있는 간격의 개수를 반환해야 합니다.
예를 들어, 입력이 [[1,4], [3,6], [2,8]]이라면 출력은 2가 됩니다. 간격 [3,6]은 [1,4]와 [2,8] 두 간격에 의해 덮여 있기 때문입니다.
해결 접근 방법
이 문제는 정렬과 스택(stack)을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- 간격 목록을 끝나는 시간(b)을 기준으로 오름차순 정렬합니다.
- 스택 st를 하나 선언합니다.
- i를 0부터 배열 크기 - 1까지 순회하며 다음을 수행합니다.
- 스택이 비어 있거나, a[i]가 스택 최상단(top) 간격과 겹치지 않는 경우 → a[i]를 스택에 삽입합니다.
- 그렇지 않은 경우 → temp = a[i]로 저장한 뒤, 스택이 비어 있지 않고 temp가 스택 최상단 간격과 겹치는 동안 계속 pop하고, 마지막에 temp를 스택에 삽입합니다.
- 최종적으로 스택의 크기를 반환합니다. 이것이 곧 남은 간격의 개수입니다.
두 간격이 서로 포함 관계에 있는지 판단하는 기준은 다음과 같습니다. 한 간격이 다른 간격 안에 완전히 들어가면(시작점이 더 크거나 같고, 끝점이 더 작거나 같으면) 해당 간격은 제거 대상이 됩니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 과정을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool intersect(vector <int>& a, vector <int>& b){
return (b[0] <= a[0] && b[1] >= a[1]) || (a[0] <= b[0] && a[1] >= b[1]);
}
static bool cmp(vector <int> a, vector <int> b){
return a[1] < b[1];
}
void printVector(vector < vector <int> > a){
for(int i = 0; i < a.size(); i++){
cout << a[i][0] << " " << a[i][1] << endl;
}
cout << endl;
}
int removeCoveredIntervals(vector<vector<int>>& a) {
sort(a.begin(), a.end(), cmp);
stack < vector <int> > st;
for(int i = 0; i < a.size(); i++){
if(st.empty() || !intersect(a[i], st.top())){
st.push(a[i]);
}
else{
vector <int> temp = a[i];
while(!st.empty() && intersect(temp, st.top())){
st.pop();
}
st.push(temp);
}
}
return st.size();
}
};
main(){
vector<vector<int>> v = {{1,4},{3,6},{2,8}};
Solution ob;
cout << (ob.removeCoveredIntervals(v));
}입력
[[1,4],[3,6],[2,8]]
출력
2
동작 원리 및 복잡도
위 코드에서 intersect() 함수는 두 간격 중 하나가 다른 하나에 포함되는지 검사합니다. 정렬된 상태에서 새 간격이 스택 최상단 간격과 포함 관계라면, 이미 처리된 간격들도 함께 확인하여 불필요한 간격을 제거합니다.
정렬 단계에서 O(n log n), 순회 및 스택 연산에서 O(n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 스택 사용으로 인해 O(n)입니다.