[Java] LeetCode 452. Minimum Number of Arrows to Burst Balloons

[Java] LeetCode 452. Minimum Number of Arrows to Burst Balloons

 

문   제 : 

[start, end]를 가지는 정수형 2차원 배열 points가 주어진다.

풍선의 시작점과 끝점을 표시한 배열이다. 

최소한의 화살을 쏴서 풍선을 모두 터뜨려라.

단, {start <= 화살 <= end}, {1 <= points.length <= 10^5}

 

 

 

Example )

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

 

---

접   근 : 

무작위로 주어진 points 배열을 정렬한 후 Greedy 방식으로 end 점을 조정하면서 최소한의 화살 개수를 구한다.

 

---

해   결 : 

points 배열을 정렬해준다.  - start는 오름차순, end는 내림차순

가장 작은 값을 가진 start부터 기준점을 잡는다. 

기준점의 start와 end 를 각각 start, end라고 하고, 

기준점 다음에 있는 풍선의 start, end 를 startTemp, endTemp 라고 하자.

 

만약 end가 startTemp 보다 크거나 같다면, 기준 다음에 있는 풍선은 기준 풍선에 포함이 되어있는 것이다. 

한 마디로, 겹치는 부분이 있다는 소리이다.

 

여기서 겹치는 부분의 구역을 식으로 나타내면

max(start, startTemp) ~ min(end, endTemp) 가 될 것이다.

 

그 다음 풍선 또한 겹칠 수 있으므로, 이 두 개의 풍선이 겹치는 부분의 기준점 end를 최신화 해준다.

 

만약, 겹치지 않는다면 새로운 화살로 쏴서 터뜨려야 하므로, 화살의 개수를 하나 늘려주고, 기준점을 초기화 해준다.

 

---

 

 

points 배열을 정렬해준다. 

start - 오름차

end - 내림차

Arrays.sort(points, (a, b)->{
    //return o1[0]!=o2[0] ? o1[0]-o2[0] : o2[1]-o1[1]; // start 오름차순, end 내림차순
    if(a[0] == b[0]) {
        return Integer.compare(b[1], a[1]);
    }
    return Integer.compare(a[0], b[0]);
});

※ 주석 처리가 되어있는 부분으로 정렬을 할 수도 있지만, integer overflow를 방지하기 위해 밑의 방법을 사용했다.

 

 

---

 

기준점을 잡아준다. 

if(points.length == 1) return 1; // 풍선이 한 개라면 화살 1개로 바로 끝

int start = points[0][0]; // 기준점 start
int end = points[0][1]; // 기준점 end
output++;

 

 

---

 

 

전체 풍선을 돌아가면서 겹치는 풍선의 범위를 구하고 기준점을 최신화 해준다. 

겹치지 않는 풍선이라면, 새로운 기준점으로 시작해서 화살을 더 쓴다.

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

    if(end >= startTemp) {// 포함
        end = Math.min(end, endTemp); // 기준점 최신화
    }
    else{ // 안 겹침
        output++;
        end = endTemp; // 새로운 기준점
    }
}

 

---

결   과  :

class Solution {
    public int findMinArrowShots(int[][] points) {
        int output=0;
        
        Arrays.sort(points, (a, b)->{
            //return o1[0]!=o2[0] ? o1[0]-o2[0] : o2[1]-o1[1]; // start 오름차순, end 내림차순
            if(a[0] == b[0]) {
                return Integer.compare(b[1], a[1]);
            }
            return Integer.compare(a[0], b[0]);
        });

        if(points.length == 1) return 1;

        int start = points[0][0];
        int end = points[0][1];
        output++;

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

            if(end >= startTemp) {// 포함
                end = Math.min(end, endTemp);
            }
            else{
                output++;
                end = endTemp;
            }
        }

        return output;
        
    }
}