[Leetcode 아주 상세한 문제풀이] 56. Merge Interval - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 56번 문제 Merge Interval 이다.

우선 문제를 살펴보자.

 

리트코드 56번 문제 Merge Interval 링크

Merge Intervals - LeetCode

Merge Intervals - LeetCode

 

 

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
 

Constraints:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

 

 

문제 설명

문제에 대해 간략히 살펴보자. 구간 배열들이 주어지는데, 주어진 구간 배열들 중 겹치는 부분이 있다면 그 배열들을 합쳐서 (merge) 최종적으로 겹치지 않는 (non-overlapping) 배열들만 출력하라는문제다. 예를 들어 문제에서 주어진 예시 1번에서 보는 것처럼 입력된 배열 중 [1, 3] 그리고 [2, 6]이 있다면 이 두 배열은 겹치는 것이기 때문에 그 두 배열을 합쳐 [1, 6]을 리턴하면 된다. 한 가지 유의할 점은 겹치는 (overlapping)에 대한 정의인데, 문제 예시 2번에서 보는 것처럼 주어진 배열이 [1,4] 그리고 [4,5]라면 이 두 배열은 겹치지는 않지만 4에서 연속되기 때문에 이 경우는 두 배열을 합쳐서 출력해야 한다.

문제를 이해하는데 어렵지 않기 때문에 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이전에 풀어보았던 리트코드 문제 435번에서도 설명했듯이

특정 구간 배열이 다른 구간 배열과 겹치는지 확인할 때

주어진 구간 배열들을 오름차순으로 배열하면 큰 이점을 갖는다.

구간 배열의 시작 값과 끝 값만을 서로 비교하면 두 배열이 겹치는지 안겹치는지 알 수 있기 때문이다.

 

 

겹치는 구간에 대한 판단은 다음과 같다.

예를 들어 위 그림과 같이 [1,2] (주황색), [4,6] (노란색), [5, 7] (파란색), [9,10] (녹색) 주어졌다고 하자.

이때 [4,6] 배열과 [5,7] 배열을 보면

[4,6] 배열의 끝 값 6과 [5,7] 배열의 시작 값 5를 비교했을 때

5가 6보다 작기 때문이 이 경우 두 배열은 겹친다고 판단할 수 있다.

따라서 이 경우 두 배열의 왼쪽 값을 비교해 더 작은 값을 병합된 배열의 시작값으로 업데이트 하고

두 배열의 오른쪽 값을 비교해 더 큰값을 병합된 배열의 끝 값으로 업데이트 하면 된다.

이제 문제를 풀어보도록 하자.

 

 

문제 풀이

구간 배열들을 입력받을 함수를 정의해 준다 (line 1)

만약 구간 배열이 비어있다면 아무것도 리턴하지 않고 종료한다 (line 2-3)

그리고 주어진 구간 배열들을 '시작점'을 기준으로 오름차순 정렬한다 (line 6)

우리는 최종적으로 겹치지 않는 배열들을 리턴하기 위한 변수를 하나 설정한다 (line 8)

주어진 구간 배열 개수만큼 for loop를 돌리는데 (line 9)

이때 겹치지 않는 배열들을 저장해놓은 배열 중 가장 뒤에 있는 배열의 '끝' 값 (merged[-1][1])

그 뒤에 오는 배열의 '시작'값 (intervals[i][0])을 비교해 (line 11)

만약 merged[-1][1]값이 intervals[i][0] 값 보다 같거나 크다면

비교하는 두 배열은 서로 겹치는 것이기 때문에 서로 병합해준다(line 13)

이때 중요한 것은 겹치지 않는 배열들을 저장해놓은 배열 중 가장뒤에 있는 배열의 '끝'값 (merged[-1][1])만

업데이트를 해주면 되는데 그 이유는 우리가 구하고자 하는 것이 서로 겹치지 않는 배열들이기 때문에

merged에는 이미 '시작'값 (merged[-1][o])이 들어있어 우리는'끝'값만 업데이트 해주면 된다.

만약 두 배열이 서로 겹치지 않는다면 (line 14)

비교하는 구간 배열을 merged 변수에 추가해준다 (line 16)

그리고 최종적으로 겹치지 않는 구간 배열들이 저장되어 있는 merged를 리턴해주면 된다 (line 18)   

 

 

문제 풀이 코드

def merge_intervals(intervals):
    if not intervals:
        return []
 
    # Sort the intervals based on the start time
    intervals.sort(key=lambda x: x[0])
 
    merged = [intervals[0]]
    print(merged)
    for i in range(1, len(intervals)):
        # If current interval's start time is less than or equal to the end time of the last merged interval
        if intervals[i][0] <= merged[-1][1]:
            # Merge the intervals by updating the end time of the last merged interval
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            # If they don't overlap, simply add the current interval to the merged list
            merged.append(intervals[i])
 
    return merged
 
# Test cases
intervals1 = [[1,3],[2,6],[8,10],[15,18]]
print(merge_intervals(intervals1))  # Expected output: [[1,6],[8,10],[15,18]]
 
#intervals2 = [[1,4],[4,5]]
#print(merge_intervals(intervals2))  # Expected output: [[1,5]]
 

 

 

관련 문제

리트코드 57번 Insert interval 문제 풀이 (링크)

리트코드 435번 Non-overlapping internval 문제 풀이 (링크)

 

56. Merge Interval