[2024] day 78. Leetcode 57. Insert Interval

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 17일 (일)
Leetcode daily problem

57. Insert Interval

https://leetcode.com/problems/insert-interval/description/?envType=daily-question&envId=2024-03-17

Problem

해당 문제는 정렬된 간격(intervals) 목록과 새로운 간격(newInterval)이 주어졌을 때, 새로운 간격을 정렬된 목록에 삽입하고, 겹치는 간격을 병합하는 문제이다.

여기서 주어진 intervals는 각 요소가 [start, end] 형식의 간격을 나타내는 2차원 리스트이며, newInterval 또한 [start, end] 형식의 간격이다.

Solution

array

해당 문제는 newInterval의 시작이 intervals의 마지막 요소보다 클 경우, newInterval을 intervals의 마지막에 추가하고 반환하고
intervals의 각 요소와 newInterval을 비교하면서 겹치는 부분을 찾는다.
겹치는 부분이 있으면, 겹치는 부분을 합치고 나머지 간격들을 그대로 유지해서
새로운 intervals를 반환한다.

Code

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 

Complexicity

시간 복잡도

해당 로직은 주어진 intervals의 길이에 비례하고, 각 반복문에서의 연산은 상수 시간이 소요되므로 전체적인 시간 복잡도는 O(n) 이다.

공간 복잡도

새로운 배열을 저장하기 위해 새로운 배열을 생성하고 기존의 배열이 추가되므로 공간 복잡도는 O(n)이다.

---

위 그래프를 봤을 때 정규표현식 중심에서 오른쪽으로 치우쳐져 있어서
효율적인 코드가 아니구나 싶어 다른 사람들이 풀어 놓은 솔루션을 봤는데,
해당 interval 배열을 순차적으로 돌기보다 while문을 사용해서 조건에 맞춰서 배열을 생성하고 있었다.
그래서 leetcode python solution부문에서 top 1,2 solution을 보고 다른 솔루션을 확인했다.