leetcode 452, Minimum Number of Arrows to Burst Balloons

NJW·2023년 1월 6일

코테

목록 보기

128/170

문제 설명

풍선들이 존재하는 범위가 주어질 때, 하나의 화살로 해당 범위 내의 모든 풍선을 터트릴 수 있다고 한다. 이때 사용하는 화살의 최소 개수를 구하여라.

그리디 알고리즘을 이용한다. 그리고 그리디 알고리즘은 대체적으로 정렬이 필요하다. 그러나 이때 단순히 o1[1] - o2[1]을 사용하면 안 되는데, 그 이유는 해당 값의 범위가 -2^31과 2^31 사이라 overflow가 일어날 수도 있기 때문이다.

문제 풀이

변수들
0-1. answer, 화살의 개수 즉, 정답
0-2. preEnd, 범위의 끝나는 지점. 현재 값의 시작이 preEnd를 벗어날 경우 새로운 화살이 필요하다고 생각해 answer에 1을 더해주고 preEnd의 값을 현재 값의 끝 값으로 설정한다.
여기서 answer의 초기 값이 1인 이유는 첫 번째 풍선을 무조건 포함해야 하기 때문이다(풍선을 모두 터트려야 함). 그렇기 때문에 preEnd의 값 또한 0이 아닌 첫 값의 끝 값으로 설정해야 한다.
~~만일 무조건 포함할 필요가 없다면 answer과 preEnd를 0으로 둬서 갱신하면 된다.~~
0-3, xStart와 xEnd, 현재 값의 시작과 끝 값
일단 풍선의 범위를 끝나는 지점을 기준으로 정렬을 한다. 위의 설명처럼 o[1]-o[2]는 사용하지 않는다. 그렇기에 끝나는 값이 같거나 오름차순으로 되어 있다면 -1을, 아니라면 1을 리턴해서 정렬하게 한다.
변수들을 전부 초기화해준다. preEnd에는 시작 값의 끝 값을 넣어준다.
points를 하나씩 확인해서 xStart와 xEnd를 갱신한다. 만일 범위의 끝 값보다 현재의 시작 값이 더 크면 이는 새로운 화살이 필요하다는 뜻이니 화살 값에 1을 더해주고 preEnd의 값을 현재 값이 끝 값으로 갱신해준다.

코드

class Solution {
    public int findMinArrowShots(int[][] points) {

        //단순히 o1[1]-o2[1]을 사용할 수 없다.
        //그 이유는 해당 숫자의 값이 -2^31과 2^31 사이라 Integer로 하려면 overflow가 일어난다.
        Arrays.sort(points, (o1, o2) ->{

            if(o1[1] <= o2[1]){
                return -1;
            }
            return 1;
        });

        int answer = 1;
        //이전의 끝 값
        int preEnd = points[0][1];
        int xStart, xEnd = 0;

        for(int[] p : points){
            xStart = p[0];
            xEnd = p[1];

            //만일 현재의 시작 값이 이전의 끝 값에 포함되지 않는다면
            //새로운 화살 필요함
            if(preEnd < xStart){
                answer++;
                //끝 값을 갱신
                preEnd = xEnd;
            }
        }

        return answer;
        
    }

}