리트코드 - 57. Insert Interval

리트코드 - 57. Insert Interval

출처 - https://leetcode.com/problems/insert-interval/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

다음과 같은 비중첩(intervals)이 주어집니다. 이 intervals 배열은 intervals[i] = [starti, endi] 형식으로 주어지며, 이는 i번째 interval의 시작과 끝을 나타냅니다. 또한 이 intervals 배열은 시작 값 starti 기준으로 오름차순으로 정렬되어 있습니다. 또한 [start, end] 형식의 새로운 interval newInterval이 주어지며, 이는 새로운 interval의 시작과 끝을 나타냅니다.

newInterval을 intervals에 삽입하여 intervals 배열이 여전히 시작 값 starti 기준으로 오름차순으로 정렬되고, 중첩되는 interval이 없도록 만들어야 합니다(필요시 중첩되는 interval을 병합).

삽입 후의 intervals 배열을 반환하세요.

참고로, intervals 배열을 제자리에서 수정할 필요는 없습니다. 새 배열을 만들어 반환할 수 있습니다.

 

풀이코드

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> answer = new ArrayList<>();
    int n = intervals.length;

    int p = 0;

    // 1. newInterval 앞 구간 추가
    while (p < n && intervals[p][1] < newInterval[0]) {
        answer.add(intervals[p]);
        p++;
    }

    // 2. 겹치는 구간들을 새로운 newInterval로 갱신
    while (p < n && intervals[p][0] <= newInterval[1]) {
        newInterval[0] = Math.min(intervals[p][0], newInterval[0]);
        newInterval[1] = Math.max(intervals[p][1], newInterval[1]);
        p++;
    }
    answer.add(newInterval); 

    // 3. newInterval 뒤의 구간을 추가
    while (p < n) {
        answer.add(intervals[p]);
        p++;
    }

    return answer.toArray(new int[answer.size()][]);
    }
}

코드설명

intervals에는 여러 범위가 주어지고, newInterval 범위가 주어지면 이 범위를 기존 intervals에 추가하는 문제이다.

그림으로 생각하면 이해가 쉽다.

 

문제에서 제시된 예시를 통해 그림으로 보자.

 

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

먼저 1) newInterval과 겹치지 않는 [1,2] 구간과 [12,16]이 추가될 것이다.

다음으로 2) 겹치는 구간인 [3,5], [6,7], [8,10] 모두 겹치므로 3,10 구간이 추가되면 해결된다.

 

이를 논리적으로 다시 나누면,

1) newInterval 구간보다 앞을 추가하고, 뒤의 구간을 추가한다.

2) newInterval과 겹치는 구간을 추가한다.

로 나눌 수 있다.

 

1)번은 생각보다 할만하다.

1-1) 앞의 구간을 추가하는 것 -> newInterval 의 시작구간보다 interval 끝값이 작으면 추가한다.

1-2) 뒤의 구간을 추가하는 것 -> newInterval 의 끝 구간보다 interval 시작값이 크면 추가한다.

 

2)번이 문제인데 겹치는 구간의 갱신을 interval을 기준으로 할 것인지, newInterval을 할 것인지 정해야 한다.

단순하게 생각해서 interval을 기준으로하면, 다음 interval 에서 겹치는 구간을 확인하기가 어렵다.

다른 코딩문제에서도 반복문내 기존 배열 값을 바꾸다보면 생각치 못한 문제가 발생하는데 그것과 비슷하다.

 

따라서 newInterval을 갱신하는 것이 좋겠다.

그럼 겹치는 구간을 어떻게 판단할까?

1-1 의 조건처럼 interval의 끝 값이 newInterval의 시작값보다 크거나 같다고 판단하면 될까?

크게 생각해보면 겹치는 경우는 위와같이 3가지 정도가 있을 것 같다.

먼저 첫번째의 경우엔 interval의 끝이 newInterval보다 같거나 크므로 만족한다.

두번째 경우부터 문제가 생기는데, 분명히 겹치는 구간인데 조건을 만족하지 못한다.

세번째도 마찬가지이다.

 

따라서 두,세번째를 만족하기 위해 조건 추가가 필요해보인다. interval 시작값이 newInterval의 끝값보다 같거나 크다는 조건이다.

 

1-1) 조건에서 newInterval 앞의 구간을 추가할 때 newInterval 의 시작구간보다 interval 끝값이 작으면 추가하는 조건이 있었다.

이 조건문을 통과하였다면 interval의 끝 값이 newInterval의 시작구간보다 큰 것만 남을 것이다.

즉, interval 시작값이 newInterval의 끝값보다 같거나 크다는 조건만 추가되면 된다.

 

이렇게 하고 풀이 코드를 보면 3개의 while문 조건이 1-1) -> 2) -> 1-2) 순으로 정리되어 있는 것을 볼 수 있다.

2번째 while문에서 모든 구간을 다 추가한다음 answer에 추가하는 것이 특징이다.

 

겹치는 구간을 추가할 때 배열의 크기를 알 수 없으므로 List<int[]> 자료형을 사용했다.

그런데 문제에서 요구하는 것은 2차원 배열이므로 이것을 변환해야 하는데 해당 자료형의 toArray메소드 중 오버로딩된 것을 사용했다.

파라미터로 제네릭을 받 해당 타입을 반환한다.

 

시간복잡도 - O(n)

공간복잡도 - O(n) (최대 n+1)

 

문제를 풀며 생각한 흐름과 배운 점

문제를 그림으로 그려보면 어렵지 않은데 생각보다 코드로 짜기가 난해해서 오래 걸린 문제이다.

배열 내의 요소를 바꾸려다가 매우 엉킨 스파게티 코드가 계속 나왔다.

가급적이면 배열 내의 요소를 바꾸는 것이 아니라 복사해서 써야 한다는 것을 항상 염두해두어야겠다.

 

정리

여러개의 구간이 주어질때 새로운 구간을 기존 구간에 추가하는 방법