[Array 문제] LEETCODE 57. Insert Interval

문제

https://leetcode.com/problems/insert-interval/

문제풀이

하기 코드는 이진탐색 기반으로 조건에 따라 배열 삽입을 통해 문제를 해결하는 코드이다.
s1,s2 / e1,e2를 각각 선언하는데 s1==s2인 경우 삽입 배열 시작점 기준 기존 배열과 겹침이 발생하지 않는 것이고 e1==e2인 경우 삽입 배열 끝점 기준 기존 배열과 겹침이 발생하지 않는다라고 해석하면 된다. 이 내용을 바탕으로 시작점에서 겹침이 발생하면 min값을 취하고 끝점에서 겹침이 발생하면 max값을 취하도록 하여 새로운 배열 생성 및 삽입 처리를 하면 간단히 해결 가능하다.

여기서 시작점 변수(s1,s2)는 bisect_left 로 처리하여 이상인 경우도 포함하도록 했는데 이는 왼쪽 겹침 발생시 왼쪽으로 범위 확장이 필요하기 때문이며 끝점 변수(e1,e2)의 경우는 반대 경우로 동작이 필요하기 떄문에 bisect_right로 처리하였다.

코드

import bisect
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        s1=bisect_left([item[0] for item in intervals],newInterval[0])
        s2=bisect_left([item[1] for item in intervals],newInterval[0])
        e1=bisect_right([item[0] for item in intervals],newInterval[1])
        e2=bisect_right([item[1] for item in intervals],newInterval[1])
              
        if s1==s2==e1==e2:
            return intervals[:s1]+[newInterval]+intervals[s1:]
        else:
            new_start=min(intervals[s2][0],newInterval[0])
            new_end = max(intervals[e2][1], newInterval[1]) if e1 != e2 else newInterval[1]
            return intervals[:s2]+[[new_start,new_end]]+intervals[e1:]        
                

Lookback

1. 이진 탐색시 bisect을 사용하여 O(n) 수행속도로 처리되긴 하였으나 이진탐색을 직접 구현하여 intervals 배열을 1회 순횐하지 않도록 하면 O(logN) 수준으로 속도 개선이 가능할 것으로 판단된다.