문제 개요
여러 개의 구간(interval)이 주어졌을 때, 서로 겹치는 구간들을 모두 하나로 합치는 문제를 생각해 봅시다. 예를 들어 구간 목록이 [[1,3], [2,6], [8,10], [15,18]]과 같이 주어진다면, 병합 후의 결과는 [[1,6],[8,10],[15,18]]이 됩니다.
그 이유는 [1,3]과 [2,6]이라는 두 구간이 서로 겹치기 때문입니다. 이 두 구간은 하나로 합쳐져 [1,6]이 되고, 나머지 구간들은 겹치는 부분이 없으므로 그대로 유지됩니다.
해결 알고리즘
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 구간 목록의 길이가 0이면 빈 리스트를 반환합니다.
- 퀵소트(quicksort) 방식으로 구간 목록을 시작 지점 기준으로 정렬합니다.
- 빈 스택(stack)을 만들고 첫 번째 구간
intervals[0]을 스택에 삽입합니다. - i를 1부터 구간 개수 - 1까지 반복합니다.
last_element:= 스택의 최상단(top) 요소- 만약
last_element의 끝 값이intervals[i]의 시작 값보다 크거나 같다면(즉, 두 구간이 겹친다면):last_element의 끝 값을intervals[i]의 끝 값과 비교하여 더 큰 값으로 갱신합니다.- 스택에서 요소를 꺼낸(pop) 뒤, 갱신된
last_element를 다시 스택에 넣습니다(push).
- 겹치지 않는다면
intervals[i]를 그대로 스택에 추가합니다.
- 모든 반복이 끝나면 스택을 결과로 반환합니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution(object): def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ if len(intervals) == 0: return [] self.quicksort(intervals,0,len(intervals)-1) #for i in intervals: #print(i.start, i.end) stack = [] stack.append(intervals[0]) for i in range(1,len(intervals)): last_element= stack[len(stack)-1] if last_element[1] >= intervals[i][0]: last_element[1] = max(intervals[i][1],last_element[1]) stack.pop(len(stack)-1) stack.append(last_element) else: stack.append(intervals[i]) return stack def partition(self,array,start,end): pivot_index = start for i in range(start,end): if array[i][0]<=array[end][0]: array[i],array[pivot_index] =array[pivot_index],array[i] pivot_index+=1 array[end],array[pivot_index] =array[pivot_index],array[end] return pivot_index def quicksort(self,array,start,end): if start<end: partition_index = self.partition(array,start,end) self.quicksort(array,start,partition_index-1) self.quicksort(array, partition_index + 1, end) ob1 = Solution() print(ob1.merge([[1,3],[2,6],[8,10],[15,18]]))
입력
[[1,3],[2,6],[8,10],[15,18]]
출력
[[1, 6], [8, 10], [15, 18]]
정리
이 알고리즘의 핵심은 정렬 후 순차적으로 겹침 여부를 확인하는 것입니다. 구간을 시작 지점 기준으로 정렬하면, 현재 처리 중인 구간과 다음 구간만 비교하면 되므로 전체 시간 복잡도는 정렬에 의해 결정되어 O(n log n)이 됩니다. 이후의 병합 과정은 각 구간을 한 번씩만 순회하면 되므로 O(n)입니다.