문제 개요
정렬되어 있고 서로 겹치지 않는(disjoint) 구간 목록이 주어졌다고 가정해 봅시다. 각 구간은 intervals[i] = [a, b] 형태로 표현되며, 이는 a <= x < b를 만족하는 수 x들의 집합을 의미합니다. 이때 intervals에 포함된 모든 구간과 주어진 toBeRemoved 구간 사이의 교집합을 제거한 뒤, 남은 구간들을 정렬된 상태로 반환해야 합니다.
예를 들어 입력이 [[0,2],[3,4],[5,7]]이고 toBeRemoved가 [1,6]이라면, 구간 [0,2]에서는 [1,2) 부분이, 구간 [5,7]에서는 [5,6) 부분이 잘려나가므로 최종 결과는 [[0,1],[6,7]]이 됩니다.
풀이 접근 방법
핵심 아이디어는 현재 처리 중인 구간을 제거 구간을 기준으로 왼쪽 조각과 오른쪽 조각으로 분리하는 것입니다. 이를 위해 다음 단계를 따릅니다.
- manipulate2() 헬퍼 함수를 정의합니다. 이 함수는 결과 벡터 a와 제거 구간 y를 인자로 받습니다.
- x := 벡터 a의 마지막 원소를 꺼내고, a에서 해당 원소를 삭제합니다.
- z := x (복사본 생성)
- x[0] := y[1] (오른쪽 조각의 시작점을 제거 구간의 끝으로), z[1] := y[0] (왼쪽 조각의 끝점을 제거 구간의 시작으로) 설정합니다.
- z[0] < z[1]이면 왼쪽 조각 z를 a에 삽입합니다.
- x[0] < x[1]이면 오른쪽 조각 x를 a에 삽입합니다.
- 메인 함수는 구간 목록 in과 제거 구간 t를 받습니다.
- 결과 벡터 ans를 선언하고, n := in의 구간 개수로 설정합니다.
- i를 0부터 n까지 반복합니다.
- in[i]를 ans에 삽입합니다.
- a := ans의 마지막 원소, b := t
- a[0] > b[0]이면 a와 b를 스왑하여 시작점 기준으로 정렬 관계를 맞춥니다.
- 두 구간이 교차하면 manipulate2(ans, t)를 호출하여 현재 구간을 분할·제거합니다.
- 모든 반복이 끝나면 ans를 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 동작 방식을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
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:
bool isIntersect(vector <int> a, vector <int> b){
return max(a[0], a[1]) >= min(b[0], b[1]);
}
void manipulate2(vector < vector <int> > &a, vector <int> y){
vector <int> x = a.back();
a.pop_back();
vector <int> z = x;
x[0] = y[1];
z[1] = y[0];
if(z[0] < z[1])a.push_back(z);
if(x[0] < x[1])a.push_back(x);
}
vector<vector<int>> removeInterval(vector<vector<int>>& in, vector<int>& t) {
vector < vector <int> > ans;
int n = in.size();
for(int i = 0; i < n; i++){
ans.push_back(in[i]);
vector <int> a;
vector <int> b;
a = ans.back();
b = t;
if(a[0]>b[0])swap(a, b);
if(isIntersect(a, b)){
manipulate2(ans, t);
}
}
return ans;
}
};
main(){
vector<int> v2 = {1,6};
vector<vector<int>> v1 = {{0,2},{3,4},{5,7}};
Solution ob;
print_vector(ob.removeInterval(v1, v2));
}입력
[[0,2],[3,4],[5,7]] [1,6]
출력
[[0, 1],[6, 7]]
동작 방식 요약
isIntersect() 함수는 두 구간이 겹치는지 여부를 판단하고, manipulate2() 함수는 겹치는 구간을 제거 구간 앞부분과 뒷부분으로 나누어 유효한 조각만 결과에 남깁니다. 이 과정을 입력 목록의 모든 구간에 대해 한 번씩만 수행하므로 시간 복잡도는 O(n)입니다. 입력 목록이 이미 정렬되어 있다는 전제 덕분에 결과 역시 자연스럽게 정렬된 상태가 유지됩니다.