문제 이해
서로 겹치지 않는 구간(interval)들의 집합이 주어졌다고 가정해 봅시다. 여기에 새로운 구간을 삽입해야 하며, 필요하다면 기존 구간들과 병합할 수 있습니다.
예를 들어 입력이 [[1,4],[6,9]]이고 새 구간이 [2,5]라면, [2,5]는 [1,4]와 겹치므로 두 구간이 [1,5]로 병합됩니다. 따라서 최종 출력은 [[1,5],[6,9]]가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 새 구간을 기존 구간 리스트의 맨 끝에 추가합니다.
- 구간 리스트를 시작 지점(start)을 기준으로 오름차순 정렬합니다. n := 구간의 총 개수입니다.
- 결과를 담을 배열 ans를 생성하고, 첫 번째 구간을 ans에 넣습니다.
- index := 1로 초기화합니다.
- index < n인 동안 다음을 반복합니다.
- last := ans의 크기 - 1 (ans의 마지막 원소 인덱스)
- 만약 max(ans[last][0], ans[last][1]) < min(intervals[index][0], intervals[index][1])이라면, 현재 구간이 마지막 구간과 겹치지 않으므로 intervals[index]를 ans에 그대로 추가합니다.
- 그렇지 않다면(두 구간이 겹친다면) 병합을 수행합니다.
- ans[last][0] := min(ans[last][0], intervals[index][0])
- ans[last][1] := max(ans[last][1], intervals[index][1])
- index를 1 증가시킵니다.
- 모든 반복이 끝나면 ans를 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
static bool cmp(vector <int> a, vector <int> b){
return a[0]<b[0];
}
vector<vector <int>>insert(vector<vector <int> >& intervals, vector <int>& newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end(),cmp);
int n = intervals.size();
vector <vector <int>> ans;
ans.push_back(intervals[0]);
int index = 1;
while(index<n){
int last = ans.size()-1;
if(max(ans[last][0],ans[last][1])<min(intervals[index][0],intervals[index][1])){
ans.push_back(intervals[index]);
} else {
ans[last][0] = min(ans[last][0],intervals[index][0]);
ans[last][1] = max(ans[last][1],intervals[index][1]);
}
index++;
}
return ans;
}
};
main(){
vector<vector<int>> v = {{1,4},{6,9}};
vector<int> v1 = {2,5};
Solution ob;
print_vector(ob.insert(v, v1));
}입력
[[1,4],[6,9]] [2,5]
출력
[[1, 5],[6, 9]]
복잡도 분석
시간 복잡도
새 구간을 추가한 후 정렬하는 데 O(n log n)이 소요되고, 이후 모든 구간을 한 번씩 순회하는 데 O(n)이 걸립니다. 따라서 전체 시간 복잡도는 O(n log n)입니다.
공간 복잡도
병합된 결과를 저장하기 위한 ans 배열에 최대 n개의 구간이 저장될 수 있으므로, 추가 공간 복잡도는 O(n)입니다.
마무리
이 알고리즘의 핵심은 새 구간을 포함한 전체 구간을 시작 지점 기준으로 정렬한 뒤, 인접한 구간끼리 겹침 여부를 검사하며 순차적으로 병합하는 것입니다. 정렬된 상태에서 한 번의 선형 순회만으로 모든 병합을 처리할 수 있기 때문에 구현이 단순하면서도 안정적인 성능을 보장합니다.