Leet code (Medium) : 452. Minimum Number of Arrows to Burst Balloons - JAVA

 

처음에 매우 복잡하게 생각했던 문제다. 

그냥 단순히 겹치는 구간이 있는건 하나로 묶인다고 생각하고,
총 몇개의 묶음구간이 있는지 구하는 것과 같다.

그래서 끝점 기준으로 오름차순 정렬한 후, 현재까지의 겹치는 구간의 끝점을 기억하고 진행하는 것이 포인트다.
현재 구간의 시작점이 그 보다 크면 현재 구간부터 새로운 묶음이 시작되어야 한다는 것이다.

 

 

추가로, 잊고 있었는데

Arrays.sort(arr, (a,b) -> a[1]-b[1]);

를 쓰면 비교대상 값이 음수인 경우 오버플로가 발생할 수 있어서, 안전하게

Arrays.sort(arr, (a,b) -> Integer.compare(a[1],b[1]));

를 쓰는 것이 좋다.

 

class Solution {
    public int findMinArrowShots(int[][] points) {
        int res = 1;

        // 끝점기준 오름차순 정렬 (겹치는 부분을 상세히 알아야해서)
        Arrays.sort(points, (a,b) -> Integer.compare(a[1], b[1])); 
        // a[1] - b[1] 는 값 중 하나가 음수면 오버플로가 발생할 수 있어서
        // Integer.compare(a[1], b[1]) 를 쓰는 것이 안전하다.

        int end = points[0][1];

        for(int i = 1; i < points.length; i++){
            int nowStart = points[i][0];
            int nowEnd = points[i][1];

            // 지금까지 구간들의 중복 구간과 겹치지 않는 구간일 때
            if(end < nowStart){
                end = nowEnd;
                res++;
            }
        }

        return res;
    }
}