Insert Interval
[문제]
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.
[입력 조건]
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
[내 풀이]
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
result = []
i = 0
n = len(intervals)
# 합병 전 구간 판단 후 추가
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# 합병 구간 추가
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# 남은 부분 추가
while i < n:
result.append(intervals[i])
i += 1
return result
해결 방법
🎯 문제 소개
먼저 문제를 간단히 설명하자면, 이미 정렬된 구간들의 리스트가 주어지고, 여기에 새로운 구간을 삽입해야 해요. 그런데 단순히 삽입하는 게 아니라, 겹치는 구간이 있으면 병합도 해야 하죠.
🤔 접근 방법
처음에는 어떻게 풀어야 할지 막막했어요. 하지만 차근차근 생각해보니, 이 문제를 세 단계로 나눌 수 있다는 걸 깨달았습니다:
- 새 구간 이전의 구간들 처리
- 새 구간과 겹치는 구간들 병합
- 새 구간 이후의 구간들 처리
이렇게 나누니 문제가 훨씬 단순해 보였어요.
💡 해결 과정
새 구간보다 완전히 앞에 있는 구간들은 그대로 결과 리스트에 추가해요.
새 구간과 겹치는 구간들을 만나면, 이들을 모두 병합해요. 시작점은 가장 작은 값으로, 끝점은 가장 큰 값으로 업데이트하면 돼요.
병합이 끝나면 병합된 새 구간을 결과 리스트에 추가해요.
마지막으로, 남은 구간들을 결과 리스트에 추가하면 끝!
😊 배운 점
복잡해 보이는 문제도 작은 단계들로 나누면 훨씬 쉬워져요.
구간을 다루는 문제에서는 '겹침'을 잘 처리하는 게 핵심이에요.
한 번의 순회로 모든 작업을 처리할 수 있다는 점이 효율적이에요.
사고 흐름을 조금 더 자세히 쓰고 친근한 말투로 바꿔보았다.
