문제 소개
구간(interval)들의 배열이 주어져 있고, 각 구간 i에 대해 시작점이 구간 i의 끝점보다 크거나 같은 다른 구간 j가 존재하는지 확인해야 합니다. 이때 구간 j를 구간 i의 "오른쪽(right)"에 있다고 표현합니다.
모든 구간 i에 대해, 조건을 만족하는 구간 j 중에서 시작점이 가장 작은 구간의 인덱스를 저장해야 하며, 만약 조건을 만족하는 구간이 하나도 없다면 -1을 저장합니다. 최종적으로 각 구간에 저장된 값을 배열 형태로 출력하면 됩니다.
예를 들어 입력이 [[3,4], [2,3], [1,2]]라면 출력은 [-1, 0, 1]이 됩니다.
- [3,4]: 끝점 4 이상의 시작점을 가진 구간이 없으므로 -1
- [2,3]: 끝점 3 이상의 시작점을 가진 구간 중 [3,4]의 시작점이 가장 작으므로 0
- [1,2]: 끝점 2 이상의 시작점을 가진 구간 중 [2,3]의 시작점이 가장 작으므로 1
접근 방법
이 문제는 C++ STL의 std::map과 lower_bound() 함수를 활용하면 효율적으로 해결할 수 있습니다. map은 키를 기준으로 항상 정렬된 상태를 유지하기 때문에, "특정 값 이상인 키 중 가장 작은 키"를 O(log n) 시간 안에 찾아낼 수 있습니다.
풀이 단계
- n := 구간 배열의 크기로 설정하고, 크기가 n인 배열 ret을 -1로 초기화하여 생성한 뒤, 맵 m을 생성합니다.
- i를 0부터 구간 배열의 크기까지 반복합니다.
- intervals[i][0](시작점)이 이미 m에 존재한다면 다음 구간으로 건너뜁니다.
- m[intervals[i][0]] := i + 1 (시작점을 키로, 인덱스 + 1을 값으로 저장)
- i를 n-1부터 0까지 역순으로 반복합니다.
- it := intervals[i][1](끝점)보다 작지 않은 키 중 가장 작은 키-값 쌍을 가리키는 반복자(lower_bound의 결과)
- 조건을 만족하는 키가 없다면(it가 end()를 가리키면) 다음 반복으로 넘어갑니다.
- ret[i] := it가 가리키는 값 - 1
- ret을 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void print_vector(vector<T> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> ret(n, -1);
map<int, int> m;
// 시작점을 키로, (인덱스 + 1)을 값으로 저장
for(int i = 0; i < n; i++){
if(m.count(intervals[i][0])) continue;
m[intervals[i][0]] = i + 1;
}
// 끝점 이상인 시작점 중 가장 작은 것을 탐색
for(int i = n - 1; i >= 0; i--){
map<int, int>::iterator it = m.lower_bound(intervals[i][1]);
if(it == m.end()) continue;
ret[i] = it->second - 1;
}
return ret;
}
};
int main(){
vector<vector<int>> v = {{3,4},{2,3},{1,2}};
Solution ob;
print_vector(ob.findRightInterval(v));
}실행 결과
입력:
[[3,4],[2,3],[1,2]]
출력:
[-1, 0, 1]
복잡도 분석
시간 복잡도: 맵을 구성하는 데 O(n log n)이 걸리고, 각 구간마다 lower_bound 탐색에 O(log n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다.
공간 복잡도: 맵과 결과 배열을 위해 O(n)의 추가 공간이 필요합니다.