leetcode medium : Insert Interval

Insert Interval - LeetCode

Insert Interval - LeetCode

 

어제 풀었던 문제의 연장선인거같다.

만약 이게 google의 코딩 인터뷰 문제였으면 어제 푼 문제를 첫 문제로 제시하고 다 풀었을 때 이런 상황을 주는 식으로 했을거같다 ㅋㅋㅋ

 

이번 문제는 진짜 구글 코딩인터뷰 본다고 생각하고 살짝 중얼중얼 설명하면서 해봤다. (가족들 있는데 혼자 중얼거리니까 살짝 뻘줌 ㅎㅎ)

 

처음에 생각한건 intervals가 start 기준으로 오름차순 정렬되어있으니 binary search로 newInterval이 삽입될 부분을 찾아서 merge하는 거였는데 로직이 복잡해지기도 하고 어디까지 merge해야될지 찾아서 merge하는 과정에서 삽입 삭제 연산이 자주 일어나면서 시간복잡도 측면에서도 좋지 않다고 느꼈다.

 

그래서 빈 result 리스트를 하나 만들고 intervals를 검사해가면서 newInterval이랑 겹치면 그때그때 유동적으로 합치고 빈 result 리스트에 추가해야겠다고 느꼈다.

 

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    
        appended = False
        result = []
        
        for interval in intervals:
            if interval[1] < newInterval[0]: #지금 검사중인 interval이 newInterval보다 명백히 앞에있는경우
                result.append(interval)
            elif interval[0] > newInterval[1]: #지금 검사중인 interval이 newInterval보다 명백히 뒤에있는경우
                if not appended: #새 인터벌이 append 되지 않았으면
                    result.append(newInterval)
                    appended = True
                result.append(interval)
            else: # 지금 검사중인 interval과 newInterval이 겹치는 경우
                newInterval[0] = min(newInterval[0], interval[0])
                newInterval[1] = max(newInterval[1], interval[1])
        
        if not appended:
            result.append(newInterval)
        
        return result