452. Minimum Number of Arrows to Burst Balloons

문제

그리디 알고리즘 문제였다. 풍선의 위치(지름)가 범위로 표현되어 주어진다. 여러 풍선이 주어지고, 최대한 적은 갯수의 화살로 모든 풍선을 터트리는 문제였다. 풍선은 겹칠 수 있다(위치 범위가 일부 겹칠 수 있다).

 

그리디 알고리즘이란 Greedy(탐욕, 욕심쟁이) 이름 처럼 지금 당장 최적의 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다.

 

링크: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons

Solution 1

class Solution {
    public int findMinArrowShots(int[][] points) {
        int answer = 1;
        Arrays.sort(points, Comparator.comparingInt(o -> o[0]));
        int start = points[0][0];
        int end = points[0][1];
        for(int i = 1; i< points.length; i++) {
            int[] cur = points[i]; 

            start = Math.max(cur[0],start);
            end = Math.min(cur[1], end);

            if(start>end) {
                start = cur[0];
                end = cur[1];
                answer++;
            }
        }
        return answer;
    }
}

화살의 위치를 이동하며 최적의 화살 개수를 도출 가능한지 시도해보았다. 인접한 풍선의 위치 범위가 겹치는 경우, 동일한 화살을 사용할 수 있고, 겹치지 않으면 화살이 추가로 필요하다 사실을 알게 됐다.

이를 위해 풍선 위치 배열인 points를 정렬하여, 각 풍선의 위치를 순차적으로 탐색하고 인접한 풍선 간의 겹침 여부를 쉽게 확인할 수 있도록 하였다.

start = Math.max(cur[0],start);
end = Math.min(cur[1], end);
            
if(start>end) {
                start = cur[0];
                end = cur[1];
                answer++;