[Java] LeetCode 57. Insert Interval

[Java] LeetCode 57. Insert Interval

 

문   제 : 

정수형 2차원 배열 intervals[i] = [start(i), end(i)] 와 1차원 배열 newIntervals = [start, end] 가  주어진다.

intervals 배열에서 newInterval에 주어진 범위에 오버랩 되는 부분을 제거해라.

오버랩 되는 기준  :  start <= i < end.

 

만약 오버랩되는 부분이 잘리고 나서 원소의 개수가 홀수가 되면

newInterval에 속하지 않으면서 가장 가까운 값을 대체 삽입한다.

 

 

You are given an array of non-overlapping intervals intervals where 
intervals[i] = [start(i), end(i)] 
represent the start and the end of the ith interval and intervals is 
sorted in ascending order by start(i). 

You are also given an interval 
newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is 
still sorted in ascending order by start(i) and intervals still does not have any overlapping intervals 
(merge overlapping intervals if necessary).

Return intervals after the insertion.

 

Example )

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

Explanation: 
Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

---

접   근 : 

int[]를 값으로 가지는 ArrayList를 생성해준다. -> 2차원 정수 배열을 표현하기 위함

newInterval을 변경하면서 ArrayList에 값을 추가 해준다.

 

---

해   결 : 

intervals의 배열 원소를 돌면서 newInterval의 범위에 드는지 안 드는지 확인한다.

 

만약 범위 보다 작다면 그대로 List에 추가해준다.

 

만약 범위 안에 들면 newInterval을 최신화 해준다.

※최신화 방법 : 

범위 안에 드는 interval[i]와 현재 newInterval을 비교해 더 작고 더 큰 값을 새로운 newInterval로 설정한다.

 

만약 범위보다 크다면 newInterval을 List에 추가해주고 새롭게 newInterval을 설정해준다.

 

---

 

int[] 를 원소로 갖는 ArrayList를 선언해준다.

List<int[]> list = new ArrayList<>();

 

 

---

 

만약 intervals[i]가 newIntervals의 범위보다 아예 작은 경우

그냥 List에 추가해준다.

if(intervals[i][1] < newInterval[0]) { // intervals의 배열이 newInterval 범위보다 작을 때
    list.add(intervals[i]);
}

 

---

 

만약 intervals[i]가 newIntervals의 범위보다 클 경우

newInterval을 list에 추가해준다.

그리고 지금의 intervals로 다시 newInterval을 설정해준다.

 

else if(intervals[i][0] > newInterval[1]) { // intervals의 배열이 newInterval 범위보다 클 때
    list.add(newInterval);
    newInterval = intervals[i]; // 다음 newInterval을 설정 
}

 

---

 

만약 intervals[i]가 newInterval 범위 안에 들 경우

newInterval을 다시 설정해준다. -> 즉, 오버랩해준다. (스킵하는 효과)

 

else if(intervals[i][1] >= newInterval[0]) { // intervals의 배열이 newInterval 범위 안에 겹칠 때 -  newInterval 다시 설정
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
}

 

---

 

반복문이 끝나면 List에 마지막으로 설정된 newInterval을 추가해주고

List를 다시 Array로 변환해서 return 해준다.

list.add(newInterval); 

// list 를 다시 Array로 변환
int[][] res = new int[list.size()][2];
for (int i = 0; i < list.size(); i++) {
	res[i] = list.get(i);
}

return res;

 

---

결   과  :

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


        for(int i=0; i<intervals.length; i++){
            
            if(intervals[i][1] < newInterval[0]) { // intervals의 배열이 newInterval 범위보다 작을 때
                list.add(intervals[i]);
            } 
            
            else if(intervals[i][0] > newInterval[1]) { // intervals의 배열이 newInterval 범위보다 클 때
                list.add(newInterval);
                newInterval = intervals[i]; // 다음 newInterval을 설정 
            }

            else if(intervals[i][1] >= newInterval[0]) { // intervals의 배열이 newInterval 범위 안에 겹칠 때 -  newInterval 다시 설정
                newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
                newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            }
        }
        list.add(newInterval); 

        // list 를 다시 Array로 변환
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
        
    }
}