문제 개요
각 행이 [시작, 끝] 형태의 포함 범위를 나타내는 2차원 숫자 리스트 intervals가 주어져 있다고 가정해 봅시다. 구간 [a, b](a < b)의 크기는 (b − a)로 정의됩니다.
여기서 우리는 이 목록에 간격(interval)을 하나 추가해야 합니다. 조건은 새로운 간격까지 모두 병합했을 때 정확히 하나의 연속된 범위만 남아야 한다는 것입니다. 이때 추가해야 할 간격의 최소 크기를 구하는 것이 문제입니다.
예를 들어 입력이 다음과 같다면,
intervals = [[15, 20],[30, 50]]
출력은 10이 됩니다. [20, 30]이라는 간격을 추가하면 두 구간이 하나의 연속 범위 [15, 50]로 합쳐지며, 이보다 작은 간격으로는 요구 조건을 만족할 수 없기 때문입니다.
접근 방법: 이벤트 기반 스윕(Sweep)
이 문제는 각 좌표 지점에서 시작/종료 이벤트를 기록한 뒤 시간순으로 정렬하면서 현재 덮인 상태를 추적하는 스윕 라인(sweep line) 기법으로 해결할 수 있습니다. 상태가 0(덮이지 않음)에서 벗어나기 전 마지막 지점과 다시 0이 되는 지점 사이가 바로 채워야 할 빈 공간입니다.
단계별 절차는 다음과 같습니다.
- events라는 새 리스트를 생성합니다.
- intervals에 있는 각 시작 시간 s와 종료 시간 e에 대해:
- (s, 1)을 events의 끝에 삽입합니다.
- (e, -1)을 events의 끝에 삽입합니다.
- events 리스트를 오름차순으로 정렬합니다.
- curr_status := 0, last := None 으로 초기화하고, interval := [0, 0] 쌍을 준비합니다.
- events의 각 (time, status) 쌍에 대해:
- curr_status가 0이고 last 값이 존재하며 time > last라면:
- interval[0]이 아직 0이라면 interval[0] := last로 설정합니다.
- interval[1] := time으로 설정합니다.
- last := time으로 갱신합니다.
- curr_status에 status를 더해 현재 덮임 상태를 갱신합니다.
- curr_status가 0이고 last 값이 존재하며 time > last라면:
- 마지막으로 interval[1] − interval[0]을 반환합니다.
정렬 과정에서 같은 시점의 이벤트는 (time, status) 튜플 비교에 따라 종료 이벤트(-1)가 시작 이벤트(1)보다 먼저 처리되므로, 경계 지점이 겹치는 경우에도 올바르게 동작합니다.
구현 코드
class Solution:
def solve(self, intervals):
events = []
for s, e in intervals:
events.append((s, 1))
events.append((e, -1))
events.sort()
curr_status = 0
last = None
interval = [0, 0]
for time, status in events:
if curr_status == 0 and last and time > last:
if interval[0] == 0:
interval[0] = last
interval[1] = time
last = time
curr_status += status
return interval[1] - interval[0]
ob = Solution()
intervals = [[15, 20],[30, 50]]
print(ob.solve(intervals))입력
[[15, 20],[30, 50]]
출력
10
동작 원리 정리
이 알고리즘의 시간 복잡도는 이벤트 정렬에 지배적이므로 O(n log n)입니다. 시작 지점에는 +1, 종료 지점에는 -1을 부여해 누적 상태(curr_status)를 관리하면, 어떤 지점이 이미 기존 구간에 포함되어 있는지 판별할 수 있습니다. 상태가 0인 상태에서 시간이 앞으로 흐르는 구간이 발견되면 그것이 곧 채워야 할 유일한 빈틈이 되며, 해당 빈틈의 길이가 곧 추가해야 할 간격의 최소 크기입니다.