[1스4코2파] # 238. LeetCode 57. Insert Interval

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (238차)
[4코1파] 2023.01.13~ (230일차)
[1스4코1파] 2023.04.12~ (141일차)
[1스4코2파] 2023.05.03 ~ (119일차)

Today :

2023.08.29 [238일차]
LeetCode 57. Insert Interval
https://leetcode.com/problems/insert-interval/

57. Insert Interval

문제 설명

배열을 담고 있는 배열 Intervals가 주어질 때 해당 Intervals의 index(배열)은 starti, endi로 i번째 간격의 시작과 끝을 나타낸다. 해당 배열은 start를 기준으로 올므차순으로 정렬되어 있는데,
다른 간격의 시작과 끝인 newInterval = [start, end] 간격도 있따.
간격이 starti에 의해 오름찬순으로 정렬되고 간격에 겹치는 간격이 없도록 간격에 newInterval을 삽입하고 return

문제 풀이 방법

start를 기준으로 오름차순으로 정렬된 겹치지 않는 구간 리스트가 주어졌을 때,
한구 간을 리스트에 삽입해야 하고, 삽입하는 과정에서 겹치는 구간이 발생하면 병합해서 하나의 구간을 만들어야 한다.
newInterval과 기존 interval의 구간의 left와 right를 비교해주는 조건을 넣어줌

https://j-e-n-n-y.tistory.com/3 에서 가져왔는데, interval에서 newInterval과 겹치는 구간은 주어진 left와 right를 제외하고 middle에 있는 [3,5],[6,7],[8.10] 이다.
left의 기준은 newInterval[0]이 interval[1] 보다 크면 left에 위치하게 되고
right의 기준은 newInterval[1]보다 interval[0]이 크면 right에 위치하게 된다.

그외에 나머지는 newInterval과 겹치고, 병합할 때 Interval[0], newInterval[0] 왼쪽끼리의 가장 작은 값을 newInterval[0] 으로, interval[1], newInterval[1] 오른쪽 값끼리의 가장 큰 값을 newInterval[1]로 엽데이트 하면, 병합된 구간이 나오게 된다!

내 코드

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ans = []

        for i in range(len(intervals)):
            if intervals[i][0] > newInterval[1]:
                ans.append(newInterval)
                return ans + intervals[i:]
            elif intervals[i][1] < newInterval[0]:
                ans.append(intervals[i])
            else:
                newInterval = [min(intervals[i][0], newInterval[0]), max(intervals[i][1], newInterval[1])]

        ans.append(newInterval)
        return ans 
        

증빙

여담

이해 완!