LeetCode의 56번째 문제인 Merge Intervals를 함께 풀어보도록 하겠습니다.
문제
intervals[i] = [starti, endi] 형태의 구간으로 이뤄진 배열이 주어졌을 때, 겹치는 모든 구간을 병합하여 겹치는 부분이 없는 구간의 배열을 반환하라.
예제
입력: intervals = [[2, 3], [8, 9], [4, 5], [6, 7], [1, 3], [5, 6]]
출력: [[1, 3], [8, 9], [4, 7]]풀이 1
단순 무식하게 주어진 배열 내에 모든 구간이 서로 겹치는지 확인하여 가능한 최대로 많은 구간을 병합해보면 어떨까요?
두 구간이 겹치는 부분이 있으려면 첫 번째 구간이 시작점보다 두 번째 구간의 종료점이 크거나 같아야 하고, 두 번째 구간의 시작점보다 첫 번째 구간의 종료점이 크거나 같아야 합니다.
즉, 첫 번째 구간을 A, 두 번째 구간을 B라고 한다면 다음과 같은 수식을 만족해야 A와 B가 겹친다고 판단할 수 있습니다.
A[0] <= B[1] and B[0] <= A[1]이 조건을 만족하지 않으면 첫 번째 구간의 종료점보다 두 번째 구간의 시작점이 크거나, 두 번째 구간의 종료점보다 첫 번째 구간의 시작점이 크다는 뜻이므로 두 구간은 겹치는 부분이 없게 됩니다.
겹치는 부분이 있는 두 구간을 병합하려면 어떻게 해야 할까요? 병합된 구간의 시작점은 두 구간의 시작점 중 더 작은 것을 선택해야하고, 종료점은 두 구간의 종료점 중 더 큰 것을 선택해야겠죠?
[min(A[0], B[0]), max(A[1], B[1])]이렇게 해줘야 두 개의 구간을 모두 아우르는 병합 구간을 얻을 수 있을 것입니다.
자 그럼, 이 두 가지 기본 로직을 염두해두고 문제에서 주어진 배열을 통해서 함께 생각을 해보겠습니다.
먼저 입력 배열의 첫 번째 구간인 [2, 3]을 상대로 두 번째 구간부터 마지막 구간까지 겹치는 부분이 있는 구간을 찾아서 병합해보겠습니다.
다섯 번째 구간인 [1, 3]과 겹치는 부분이 있네요.
[2, 3]과 [1, 3]을 병합한 결과인 [1, 3]으로 첫 번째 구간을 대체하고, 병합된 5번째 구간을 제거하겠습니다.
v
[[2, 3], [8, 9], [4, 5], [6, 7], [1, 3], [5, 6]]
^
[2, 3] + [1, 3] = [min(2, 1), max(3, 3)] = [1, 3]
v
[[1, 3], [8, 9], [4, 5], [6, 7], [5, 6]]병합된 구간인 [1, 3]과는 더 이상 겹치는 부분이 있는 구간이 배열에 없는 것 같으니 다음 구간으로 넘어가겠습니다.
다음에는 두 번째 구간인 [8, 9]을 상대로 세 번째 구간부터 마지막 구간까지 겹치는 부분이 있는 구간을 찾아서 병합해보겠습니다.
[8, 9]와는 겹치는 분이 있는 구간이 없으므로 다음 구간으로 넘어가겠습니다.
v
[[1, 3], [8, 9], [4, 5], [6, 7], [5, 6]]다음에는 세 번째 구간인 [4, 5]를 상대로 네 번째 구간부터 마지막 구간까지 겹치는 부분이 있는 구간을 찾아서 병합해보겠습니다.
마지막 구간인 [5, 6]과 겹치는 부분이 있네요.
[4, 5]과 [5, 6]을 병합한 결과인 [4, 6]으로 세 번째 구간을 대체하고, 병합된 마지막 구간을 제거하겠습니다.
v
[[1, 3], [8, 9], [4, 5], [6, 7], [5, 6]]
^
[4, 5] + [5, 6] = [min(4, 5), max(5, 6)] = [4, 6]
v
[[1, 3], [8, 9], [4, 6], [6, 7]]병합된 구간인 [4, 6]과 겹치는 부분이 있는 구간이 있는지 확인해보니 마지막 구간인 [6, 7]이 겹친다는 것을 알 수 있네요.
(이전 단계에서 병합하기 전 [4, 5]일 때는 [6, 7]과 겹치는 구간이 없었는데 [5, 6]과 병합한 후에 [6, 7]과 겹치는 부분이 생겼네요!)
[4, 6]과 [6, 7]을 병합한 결과인 [4, 7]로 세 번째 구간을 대체하고, 병합된 마지막 구간을 제거하겠습니다.
v
[[1, 3], [8, 9], [4, 6], [6, 7]]
^
[4, 6] + [6, 7] = [min(4, 6), max(6, 7)] = [4, 7]
v
[[1, 3], [8, 9], [4, 7]]자 이렇게 최종적으로 겹치는 부분이 없는 3개의 구간을 얻게 되었습니다!
이 Brute force 알고리즘은 막상 코드로 구현하려면 생각했던 것보다 까다롭게 느껴지실 수 있는데요. 위에서 알고리즘을 개념적으로 설명드릴 때는 배열해서 병합된 구간을 제거하였지만, 구현 코드에서는 집합(set) 자료구조를 사용하여 병합된 구간을 다시 고려하는 것을 방지해주고 있습니다.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
output = []
visited = set()
for i in range(len(intervals)):
if i in visited:
continue
visited.add(i)
while True:
has_merged = False
for j in range(len(intervals)):
if j in visited:
continue
if (
intervals[i][0] <= intervals[j][1]
and intervals[j][0] <= intervals[i][1]
):
visited.add(j)
intervals[i] = [
min(intervals[i][0], intervals[j][0]),
max(intervals[i][1], intervals[j][1]),
]
has_merged = True
if not has_merged:
break
output.append(intervals[i])
return output이 풀이의 시간 복잡도는 모든 구간에 대해서 다른 모든 구간과 병합이 가능한지 확인하므로 O(n^2)이 됩니다.
반면 공간 복잡도는 O(n)이 되는데요.
세트의 크기가 입력 배열의 크기만큼 커지는데다가 결과 배열의 크기도 최악의 경우 겹치는 구간이 없어서 입력 배열의 크기가 동일해지기 때문입니다.
풀이 2
사실 이 문제는 정렬을 사용하면 훨씬 더 간단하면서도 효율적으로 해결할 수 있습니다. 왜냐하면 주어진 배열을 구간의 시작점을 기준으로 정렬하게 되면 단순히 이웃하고 있는 구간만 확인해도 되기 때문입니다.
예를 들어, 위에서 사용했던 동일한 예제 배열을 정렬해볼께요.
[1, 3], [2, 3], [4, 5], [5, 6], [6, 7], [8, 9]그럼 자연스럽게 병합이 가능한 구간끼리 그룹이 나눠지는 것이 보이시지 않나요?
[1, 3], [2, 3] ✂️ [4, 5], [5, 6], [6, 7] ✂️ [8, 9]이렇게 겹치는 부분이 있는 구간끼리 병합해주면 결국 다음과 같이 3개의 구간을 얻게 될 거에요.
[1, 3] ✂️ [4, 7] ✂️ [8, 9]이렇게 정렬이 도움이 될 거라는 것을 직관적으로 알았다면 좀 더 알고리즘적으로 사고를 해보겠습니다.
입력 배열과 별도의 배열에 병합된 결과를 저장할 건데요. 입력 배열을 루프를 돌면서 현재 구간이 결과 배열에 저장되어 있는 마지막 구간과 병합할 수 있다면 병합하고 없다면 현재 구간을 결과 배열에 추가합니다.
입력 배열 = [1, 3], [2, 3], [4, 5], [5, 6], [6, 7], [8, 9]
결과 배열 = []맨 처음에는 결과 배열이 비어있어서 마지막 구간이 없으므로 현재 배열을 그냥 결과 배열에 넣고 시작할께요.
입력 배열 = [1, 3], [2, 3], [4, 5], [5, 6], [6, 7], [8, 9]
^
결과 배열 = [[1, 3]]마지막 구간 [1, 3]와 현재 구간 [2, 3]은 겹치는 부분이 있으므로 두 구간을 병합합니다.
입력 배열 = [1, 3], [2, 3], [4, 5], [5, 6], [6, 7], [8, 9]
^
[1, 3] + [2, 3] = [min(1, 2), max(3, 3)] = [1, 3]
결과 배열 = [[1, 3]]마지막 구간 [1, 3]와 현재 구간 [4, 5]는 겹치는 부분이 없으므로 현재 구간을 결과 배열에 추가합니다.
입력 배열 = [1, 3], [2, 3], [4, 5], [5, 6], [6, 7], [8, 9]
^
결과 배열 = [[1, 3], [4, 5]]마지막 구간 [4, 5]와 현재 구간 [5, 6]은 겹치는 부분이 있으므로 두 구간을 병합합니다.
입력 배열 = [1, 3], [2, 3], [4, 5], [5, 6], [6, 7], [8, 9]
^
[4, 5] + [5, 6] = [min(4, 5), max(5, 6)] = [4, 6]
결과 배열 = [[1, 3], [4, 6]]마지막 구간 [5, 6]와 현재 구간 [6, 7]은 겹치는 부분이 있으므로 두 구간을 병합합니다.
입력 배열 = [1, 3], [2, 3], [4, 5], [5, 6], [6, 7], [8, 9]
^
[4, 6] + [6, 7] = [min(4, 6), max(6, 7)] = [4, 7]
결과 배열 = [[1, 3], [4, 7]]마지막 구간 [5, 7]과 현재 구간 [8, 9]은 겹치는 부분이 없으므로 현재 구간을 결과 배열에 추가합니다.
입력 배열 = [1, 3], [2, 3], [4, 5], [5, 6], [6, 7], [8, 9]
^
결과 배열 = [[1, 3], [4, 7], [8, 9]]이 정렬을 이용한 알고리즘을 코드로 구현해볼까요?
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
output = []
for interval in sorted(intervals):
if not output or output[-1][1] < interval[0]:
output.append(interval)
else:
output[-1][1] = max(output[-1][1], interval[1])
return output이 풀이의 시간 복잡도는 입력 배열을 정렬하는데 O(nlog(n)) 시간이 걸리고, 입력 배열을 루프 도는데 O(n) 시간이 걸리므로 빅오 계산법에 따라 O(nlog(n)) + O(n) = O(nlog(n))이 됩니다.
반면에 공간 복잡도는 위 풀이와 동일하게 결과 배열의 크기 때문에 O(n)이 되겠네요.
마치면서
코딩 시험에서 구간(interval)을 다루는 유형의 문제에서는 이 문제가 가장 기본이 된다고 볼 수 있는데요. 본 문제를 통해 기본기를 잘 닦아놓으셔서 같은 유형의 좀 더 어려운 문제를 풀 때 큰 도움이 되었으면 좋겠습니다.
이 문제를 잘 푸셨다면 비슷하지만 좀 더 어려운 Insert Interval 문제도 풀어보시라고 추천드리고 싶습니다.
코딩 테스트에서 구간을 어떻게 다루는지에 대해서 더 공부하고 싶으시다면 관련 게시물을 추천드리겠습니다.