[leetcode - 57. Insert Interval] java

문제 설명

1. 이미 존재하는 interval 들이 있다. 이것들은 서로 겹치지 않고 오름차순으로 있다.

2. 여기에 새로운 interval 이 추가된다.

3. 새로운 interval 이 기존 interval 사이로 잘 녹아들게 하면 된다.

4. 녹아든다는건 오름차순으로 들어가고 혹시 겹치는 부분이 있으면 그걸 덥어주게 하면 됨

풀이 과정

1. 한번의 for문으로 구하는 방법은 잘 모르겠다.

2. 3개의 for문으로 나눈다. (indexing으로 진행)

3. (1) 새로운 interval보다 앞서는 부분 -> 도착점이 새 interval 앞부분보다 작은 애들은 신규 interval이랑 관계 없음

4. (2) 새로운 interval이 들어가는 부분 -> 시작점이 새 interval 뒷부분보다 크면 안겹친다.

5. 그리고, 앞부분 크기와 뒷부분 크기를 전체의 최소, 최대로 넣어주면 된다.

6. (3) 위의 부분까지 했으면 그 뒤는 또 새로운 interval과 관련이 없으니 그대로 넣어주면 된다.

구현은 쉽지만 생각을 떠올리는게 은근 어려운 느낌.

코드

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ansList = new ArrayList<>();
        int i = 0;

        // 새로 추가되는 interval 보다 앞에 있는 것들은 그냥 넣어준다.
        for(i=i; i<intervals.length; i++) {
            int[] now = intervals[i];
            if(now[1] >= newInterval[0]) break;
            ansList.add(now);
        }

        // 새로 추가되는 interval 을 중간에 넣는다.
        for(i=i; i<intervals.length; i++) {
            int[] now = intervals[i];
            if(newInterval[1] < now[0]) break; // 더이상 겹치지 않는 부분은 새로 추가되는게 지금 앞보다 이전에 있을때
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        }
        ansList.add(newInterval);

        // 나머지 넣으면 끝
        for(i=i; i<intervals.length; i++) {
            ansList.add(intervals[i]);
        }

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