여러 개의 구간(interval) 목록이 있다고 가정해 보겠습니다. 각 구간은 [시작, 끝] 형태로 표현되며, 시작 시점과 끝 시점을 모두 포함하는(inclusive) 범위를 나타냅니다. 이때 구해야 할 것은 이 구간들의 교차 구간(intersection), 즉 주어진 모든 구간에 공통으로 속하는 구간입니다.
예를 들어 입력이 [[10, 110], [20, 60], [25, 75]]라면, 세 구간 모두에 포함되는 범위는 [25, 60]이므로 출력 결과는 [25, 60]이 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 구간 목록에서 마지막 요소를 꺼내 start와 end의 초기값으로 설정합니다.
- 목록이 빌 때까지 다음 과정을 반복합니다.
- 다음 구간을 꺼내 start_temp, end_temp에 저장합니다.
- start는 기존 start와 start_temp 중 더 큰 값으로 갱신합니다.
- end는 기존 end와 end_temp 중 더 작은 값으로 갱신합니다.
- 최종적으로 [start, end] 구간을 반환합니다.
핵심 아이디어
교차 구간의 시작점은 모든 구간 시작점 중 최댓값이고, 끝점은 모든 구간 끝점 중 최솟값이라는 점이 핵심입니다. 참고로 계산 결과에서 start가 end보다 커진다면, 공통으로 겹치는 구간이 존재하지 않는다는 의미입니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, intervals):
start, end = intervals.pop()
while intervals:
start_temp, end_temp = intervals.pop()
start = max(start, start_temp)
end = min(end, end_temp)
return [start, end]
ob = Solution()
intervals = [[10, 110], [20, 60], [25, 75]]
print(ob.solve(intervals))
입력
[[10, 110], [20, 60], [25, 75]]
출력
[25, 60]
복잡도 분석
각 구간을 한 번씩만 처리하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간은 상수 수준(O(1))으로 매우 효율적인 알고리즘입니다.