문제 정의
각 구간(interval)은 (a, b) 형태로 표현되며, a는 이벤트의 시작 시간, b는 종료 시간을 나타냅니다. 주어진 구간 목록 중 하나라도 다른 구간을 완전히 포함(완전히 겹침)하는 경우에는 True를 반환하고, 그렇지 않으면 False를 반환해야 합니다.
예를 들어 입력이 [(4,6), (10,12), (7,9), (13,16)]라면 어떤 구간도 다른 구간 안에 완전히 들어가지 않으므로 결과는 False입니다. 반면 입력이 [(4,6), (4,9), (7,11), (5,8)]라면 구간 (5,8)이 구간 (4,9) 내부에 완전히 포함되므로 결과는 True입니다.
해결 접근 방식
이 문제는 정렬을 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 구간 목록을 오름차순으로 정렬합니다. 파이썬의 튜플 정렬은 첫 번째 요소(시작 시간)를 기준으로 수행되며, 시작 시간이 같으면 두 번째 요소(종료 시간)로 정렬됩니다.
- 인덱스 1부터 마지막 구간까지 순회하면서, 현재 구간의 끝점이 바로 앞 구간의 끝점보다 작거나 같은지 확인합니다.
- 조건을 만족하면 현재 구간이 앞 구간 안에 완전히 포함된 것이므로 True를 반환합니다.
- 모든 구간을 확인해도 조건을 만족하지 않으면 False를 반환합니다.
정렬 후에는 현재 구간의 시작점이 항상 이전 구간의 시작점보다 크거나 같다는 것이 보장되므로, 끝점만 비교하면 포함 여부를 판단할 수 있습니다. 즉, 현재 구간의 끝점이 이전 구간의 끝점보다 작거나 같다면 해당 구간 전체가 이전 구간 내부에 존재하는 것입니다.
구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
def solve(intervals):
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][1] <= intervals[i-1][1]:
return True
return False
intervals = [(4,6),(10,12),(7,9),(13,16)]
intervals2 = [(4,6), (4,9), (7,11), (5,8)]
print(solve(intervals))
print(solve(intervals2))입력
[(4,6),(10,12),(7,9),(13,16)] [(4,6), (4,9), (7,11), (5,8)]
출력
False True
복잡도 분석
이 알고리즘의 시간 복잡도는 정렬 단계가 지배적이므로 O(n log n)입니다. 정렬 이후의 순회는 선형 시간 O(n)으로 처리되며, 공간 복잡도는 정렬에 필요한 추가 공간을 제외하면 O(1)입니다. 구간 개수가 많아져도 효율적으로 동작하는 장점이 있습니다.