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

Leetcode 문제

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

우선 문제를 살펴보자.

 

리트코드 57번 문제 Insert Interval 링크

Insert Interval - LeetCode

Insert Interval - LeetCode

 

 

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
 
Constraints:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 105

 

 

문제 설명

문제를 간략히 살펴보자. 시작 점과 끝 지점으로 이루어진 배열이 주어진다. 인풋으로 이 배열이 2개 이상 주어지는데, 이때 시작 점과 끝 새로운 이루어진 새로운 배열이 주어졌을 때 이 새로운 배열을 기존 배열에 끼어 넣되 오름차순이 되도록 끼어 넣어야 한다는 것이다.

예를 들어 문제 예시 1번 에서 주어진 것 처럼 1부터 3 그리고 6부터 9로 구간을 나타내는 배열이 주어졌고 (녹색) 새로운 배열 2부터 5가 주어진 경우 (노란색) 아래와 같이 표현할 수 있다. 이 새로운 배열은 2와 3이 겹치며 1부터 까지 연속된 구간이 되므로, 결과적으로 구간 1 (1부터 5)와 구간 2 (6부터 9) 두 개의 구간 배열을 얻을 수 있다. 설명이 조금 복잡하지만 문제를 이해하기는 어렵지 않으니 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 접근하는 방법은

주어진 여러 구간 배열 중 새로 주어진 배열을 어디에 끼워 넣을지 생각해보는 것이다.

기존 구간 배열에 새로운 구간 배열을 끼어 넣는 상황은 크게 3가지가 있다.

 

1) 기존 구간 배열이 새로운 구간 배열과 겹치지 않고 그 앞쪽에 위치할 때 (주황색)

2) 기존 구간 배열에 새로운 구간 배열이 겹칠 때 (파란색)

3) 기존 구간 배열이 새로운 구간 배열과 겹치지 않고 그 뒤쪽에 위치할 때 (녹색)

 

위 세 가지 경우의 조건을 잘 따져보면 우리가 어느 구간에 새로운 구간 배열을 넣을 지 알 수 있다.

1) 기존 구간 배열이 새로운 구간 배열과 겹치지 않고 그 앞쪽에 위치할 때 (주황색)

이 경우 주항색 배열 오른쪽 끝에 위치한 2와 노란색 배열 왼쪽 끝에 위치한 4를 비교해보면 된다.

위 경우처럼 2가 4보다 작기 때문에 두 배열은 겹치지 않으며 주황색 배열은 노란색 배열 (=새로운 배열) 왼쪽에 위치힌다.

2) 기존 구간 배열에 새로운 구간 배열이 겹칠 때 (파란색)

이 경우 파란색 배열 왼쪽 끝에 위치한 5와 노란색 배열 오른쪽 끝에 위치한 6을 비교하면 된다.

위 경우처럼 5 (파란색)가 6 (노란색) 보다 작기 때문에 이 경우 두 배열은 항상 겹칩을 알 수 있다.

따라서 이 경우 두 배열을 병합해주면 된다.

단, 병합할 시 왼쪽 끝 구간은 파란색 배열과 노란색 배열 왼쪽 끝 값 (5와 4)들을 비교해 작은 걸 선택하고

오른쪽 끝 구간은 파란색 배열과 노란색 배열 오른쪽 끝 값 (7과 6)들을 비교해 큰 값을 선택해야 한다.

3) 기존 구간 배열이 새로운 구간 배열과 겹치지 않고 그 뒤쪽에 위치할 때 (녹색)

이 경우 녹색 배열 왼쪽 끝에 위치한 9와 노란색 배열 오른쪽 끝에 위치한 6를 비교해보면 된다.

위 경우처럼 9가 6보다 작기 때문에 두 배열은 겹치지 않으며 녹색 배열은 노란색 배열 (=새로운 배열) 오른쪽에 위치힌다.

이제 위 3가지 경우의 수를 코드로 표현해 보자.

 

 

문제 풀이

기존 구간 배열과 새로운 구간 배열을 입력받을 함수를 정의해 준다 (line 1)

병합 후 얻게되는 구간 배열을 저장하기 위한 리스트를 하나 만들어 준다 (line 2)

첫번째로 기존 구간 배열 중 새로운 구간 배열 왼쪽에 있는 구간 배열을 찾아낸다.

기존 구간 배열 개수만큼 while loop를 돌리며 위에서 설명한대로

기존 구간 배열 오른쪽 값과 새로운 구간 배열 왼쪽 값을 비교해

새로운 구간 배열 왼쪽 값이 기존 구간 배열 오른쪽 값보다 큰 경우 (line 6)

두 배열은 겹치지 않기 때문에 기존 구간 배열을 앞서 만들어준 merge 리스트에 넣어둔다.

두번째 경우는 기존 구간 배열과 새로운 구간 배열이 겹치는 경우다.

앞서 설명한대로 기존 구간 배열의 왼쪽 값과 새로운 구간 배열 오른쪽 값을비교해

새로운 구간 배열 오른쪽 값이 기존 구간 배열 왼쪽 값보다 크다면(line 11)

두 배열을 겹치는 것이므로 병합을 해준다.

이때 병합된 배열의 왼쪽 값은 기존 구간 배열 왼쪽값과 새로운 구간 배열 왼쪽값 중 작은값 (line 12)

그리고 오른쪽 값은 기존 구간 배열 오른쪽값과 새로운 구간 배열 오른쪽값 중 큰값을 선택한다 (line 13)

그리고 병합된 구간 배열을 merge에 추가한다 (ine 16)

마지막으로 기존 구간 배열이 새로운 구간 배열보다 오른쪽에 있는 경우인데

앞의 두 경우를 이미 탐색했으므로 기존 구간 배열에 남아있는 배열은

새로운 구간 배열 오른쪽에 위치한다고 생각할 수 있다. (line 19)

따라서 이 배열들을 merge 리스트에추가한다(line 20)

그리고 마지막에 겹치지 않는 구간 배열 및 병합된 배열을 넣어둔 merge 리스트를 리턴한다.

 

 

문제 풀이 코드

def insert_interval(intervals, newInterval):
    merged = []
    i = 0
    
    # Add all intervals that come before the newInterval
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1
 
    # Merge overlapping intervals
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        print(i)
        print(newInterval[0])
        print(newInterval[1])
        i += 1
 
    merged.append(newInterval)
 
    # Add all intervals that come after the newInterval
    while i < len(intervals):
        merged.append(intervals[i])
        i += 1
 
    return merged
 
# Example usage:
intervals1 = [[1, 3], [6, 9]]
newInterval1 = [5, 7]
print(insert_interval(intervals1, newInterval1))  # Output: [[1, 5], [6, 9]]
 
#intervals2 = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
#newInterval2 = [4, 8]
#print(insert_interval(intervals2, newInterval2))  # Output: [[1, 2], [3, 10], [12, 16]]
 

 

 

관련 문제

리트코드 56번 Merge interval 문제 풀이 (링크)

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

 

 

57. Insert Interval