[Grind75-LeetCode] Insert Interval JAVA

반응형

728x90

[Grind75-LeetCode] Insert Interval - Medium

---

접근

• 구현

---

풀이

2차원 배열로 각 구간이 주어지고 새로운 구간이 주어질 때 병합된 최종 구간은 어떻게 되는지 구하는 문제이다. 새로운 구간과 기존 구간이 겹치는 곳만 조작을 해주면 되는 문제이다. 예제2 번을 예시로 설명하겠다.

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

기존 구간
1~2, 3~5, 6~7, 8~10, 12~16

새로운 구간
4~8

겹치는 구간
3~5, 6~7, 8~10

겹치는 구간을 연결
3~10

결과
1~2, 3~10, 12~16

이렇게 새로운 구간을 삽입하며 기존 구간과 겹치는 부분을 병합하는 것이다.

     public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

우선 배열의 크기가 달라질 수 있으니 List를 사용해 만들어 줄 것이다. 처음엔 우선 새로운 구간 전까지 겹치지 않는 부분은 그대로 다시 List에 삽입해준다.

	while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

다음은 새로운 구간과 겹치는 부분을 처리하는 과정이다. 새로운 삽입할 구간을 만들어주는데 구간의 시작은 기존 구간과 새로운 구간 중 더 작은 값을 선택하여 겹치는 구간을 포함해주고 구간의 끝 또한 더 큰 값을 선택해 겹치는 구간을 포함해준다. 처리가 끝나면 만들어진 구간을 List에 넣어준다.

	while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        
        return result.toArray(new int[result.size()][]);
    }

새로운 구간과 겹치지 않는 뒷 부분에 대한 처리이다. 남은 부분을 다 List에 넣어준 뒤 2차원 배열로 결과를 반환해준다.

---

전체 코드

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval); 
        
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        
        return result.toArray(new int[result.size()][]);
    }
}