문제 설명
구간(interval)들의 목록이 주어졌다고 가정해 보겠습니다. 목록의 각 항목 intervals[i]는 [시작(start), 끝(end)] 형태의 값을 가집니다. 우리가 구해야 할 값은 다른 구간 안에 완전히 포함되는 구간의 개수입니다. 단, 하나의 구간이 여러 구간에 동시에 포함되더라도 한 번만 계산합니다.
구간 [s0, e0]가 다른 구간 [s1, e1] 안에 완전히 포함되려면 s1 ≤ s0이고 e0 ≤ e1을 만족해야 합니다.
예를 들어 입력이 intervals = [[2, 6], [3, 4], [4, 7], [5, 5]]라면 출력은 2가 됩니다. [3, 4]는 [2, 6]에 포함되고, [5, 5]는 [4, 7]에 포함되기 때문입니다.
접근 방법
이 문제는 정렬과 한 번의 순회만으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 구간 목록이 비어 있으면 0을 반환합니다.
- 구간 목록을 시작 시간 기준으로 오름차순 정렬하되, 시작 시간이 같은 경우에는 끝 시간을 내림차순으로 정렬합니다.
- 변수 end_mx를 음의 무한대(-infinity)로 초기화하고, 정답 변수 ans를 0으로 초기화합니다.
- 정렬된 구간을 순서대로 순회하면서 각 (start, end) 쌍에 대해 다음을 수행합니다.
- 현재 구간의 end가 end_mx보다 작거나 같으면 ans를 1 증가시킵니다. 이는 해당 구간이 앞서 확인한 어떤 구간에 포함된다는 의미입니다.
- end_mx를 end_mx와 end 중 더 큰 값으로 갱신합니다.
- 순회가 끝나면 ans를 반환합니다.
동작 원리와 시간 복잡도
시작 시간을 오름차순으로 정렬하면 어떤 구간을 포함하는 구간은 항상 그 구간보다 앞에 위치하게 됩니다. 또한 시작 시간이 같을 때 끝 시간을 내림차순으로 정렬하면, 더 긴 구간이 먼저 처리되므로 짧은 구간이 누락되지 않습니다. 따라서 지금까지 확인한 끝 시간의 최댓값(end_mx)만 추적하면, 현재 구간의 끝이 그 값보다 작거나 같은지 검사하는 것만으로 포함 여부를 판단할 수 있습니다.
정렬에 O(n log n), 순회에 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)이며, 추가 공간 복잡도는 O(1)입니다.
예제 코드
다음 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
def solve(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: (x[0], -x[1]))
end_mx = float("-inf")
ans = 0
for start, end in intervals:
if end <= end_mx:
ans += 1
end_mx = max(end_mx, end)
return ans
intervals = [[2, 6],[3, 4],[4, 7],[5, 5]]
print(solve(intervals))
입력
[[2, 6],[3, 4],[4, 7],[5, 5]]
출력
2