문제 개요
구간(interval) 목록이 주어졌을 때, 서로 겹치는 구간을 하나로 병합하여 정렬된 순서의 합집합을 구하는 문제입니다.
예를 들어 입력이 inv = [[2, 5], [4, 10], [20, 25]]라면, [2, 5]와 [4, 10]이 서로 겹치므로 [2, 10]으로 병합되고, [20, 25]는 겹치지 않아 그대로 유지됩니다. 따라서 최종 출력은 [[2, 10], [20, 25]]가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 구간 목록을 먼저 오름차순으로 정렬합니다.
- 결과를 저장할 새로운 리스트(ans)를 생성합니다.
- 정렬된 구간의 각 시작점(s)과 끝점(e)에 대해 다음을 수행합니다.
- ans가 비어 있지 않고, s가 ans의 마지막 구간 끝점보다 작거나 같다면 두 구간이 겹치는 것이므로, 마지막 구간의 끝점을 e와 기존 끝점 중 더 큰 값으로 갱신합니다.
- 그렇지 않으면 새로운 구간 [s, e]를 ans에 추가합니다.
- 모든 구간을 처리한 후 ans를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 동작 방식을 확인할 수 있습니다.
class Solution:
def solve(self, intervals):
intervals.sort()
ans = []
for s, e in intervals:
if ans and s <= ans[-1][1]:
ans[-1][1] = max(ans[-1][1], e)
else:
ans.append([s, e])
return ans
ob = Solution()
inv = [[2, 5], [4, 10], [20, 25]]
print(ob.solve(inv))
입력
[[2, 5], [4, 10], [20, 25]]
출력
[[2, 10], [20, 25]]
동작 원리 및 시간 복잡도
구간을 미리 정렬하면 겹칠 가능성이 있는 구간들이 반드시 인접하게 배치됩니다. 따라서 현재 구간의 시작점이 직전에 저장한 마지막 구간의 끝점과 겹치는지만 확인하면 됩니다. 겹치는 경우에는 끝점을 더 큰 값으로 확장하고, 겹치지 않는 경우에는 새로운 구간으로 추가합니다.
이 알고리즘의 전체 시간 복잡도는 정렬 과정이 지배적이므로 O(n log n)이며, 공간 복잡도는 결과 리스트를 제외하면 O(1)로 매우 효율적입니다.