어떤 이벤트의 시작 시간과 종료 시간을 나타내는 값 쌍 (time1, time2)으로 구성된 간격(interval) 집합이 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 집합 안에서 서로 겹치는 간격이 하나라도 존재하는지 확인하는 것입니다. 만약 겹치는 간격이 있다면 True를 반환하고, 그렇지 않다면 False를 반환합니다.
예를 들어 입력이 [(4,7), (5,11), (7,11), (5,8)]이라면 출력 결과는 True가 됩니다.
문제 해결 접근 방법
이 문제는 정렬을 활용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 주어진 간격 목록(inputArr)을 시작 시간(time1)을 기준으로 오름차순 정렬합니다.
- 정렬된 목록을 순회하면서 인접한 두 간격을 비교합니다.
- 만약 이전 간격의 종료 시간(time2)이 현재 간격의 시작 시간(time1)보다 크다면, 두 간격이 겹치는 것이므로 True를 반환합니다.
- 모든 간격을 확인했는데도 겹치는 구간이 없다면 False를 반환합니다.
정렬 후에는 반드시 바로 앞의 간격과 비교하는 것만으로 충분합니다. 시작 시간 기준으로 정렬되어 있기 때문에, 이전 간격의 종료 시간이 현재 간격의 시작 시간을 넘어선다면 그 시점에 이미 겹침이 발생하기 때문입니다.
예제 코드
아래는 위 알고리즘을 C++로 구현한 예제입니다.
#include <bits/stdc++.h>
using namespace std;
class IntervalClass {
public:
int time1, time2;
};
bool compare(IntervalClass inst1, IntervalClass inst2){
return (inst1.time1 < inst2.time1) ? true : false;
}
bool solve(vector<IntervalClass> &inputArr){
int size = inputArr.size();
sort(inputArr.begin(), inputArr.end(), compare);
for (int i = 1; i < size; i++)
if (inputArr[i - 1].time2 > inputArr[i].time1)
return true;
return false;
}
int main(){
vector<IntervalClass> inputArr = {{4,7},{5,11},{7,11},{5,8}};
cout << solve(inputArr);
}입력
{{4,7},{5,11},{7,11},{5,8}}출력
1
코드 설명 및 복잡도 분석
위 코드에서 solve() 함수는 먼저 compare() 함수를 기준으로 간격 벡터를 정렬합니다. 이때 정렬은 각 간격의 시작 시간(time1)을 기준으로 수행됩니다.
정렬이 완료되면 두 번째 간격부터 마지막 간격까지 순서대로 확인하며, 직전 간격의 종료 시간이 현재 간격의 시작 시간보다 큰 경우 즉시 true를 반환합니다. 예제 입력에서는 (4,7)과 (5,11)이 이미 겹치므로 결과로 1(true)이 출력됩니다.
- 시간 복잡도: O(n log n) — 정렬에 소요되는 시간이 지배적입니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 제자리(in-place) 정렬을 사용합니다.
이처럼 정렬 기반 접근 방식을 사용하면 모든 간격 쌍을 일일이 비교하는 O(n²) 브루트포스 방식보다 훨씬 효율적으로 겹침 여부를 판별할 수 있습니다.