[LeetCode] 452번 Minimum Number of Arrows to Burst Balloons 문제를 풀어보았다. (ft. java)

2023년 01월 05일 목요일 - 왜 체했지...

오늘 올려볼 문제는 452번 Minimum Number of Arrows to Burst Balloons 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

어려울거 같았는데 생각보다는 빨리 풀림

입력

사진에서도 볼 수 있듯이 2차원 int 배열 1개가 입력으로 들어온다.

---

풀이 및 코드

주어진 point 위치만큼 차지하고 있는 풍선들이 가로로 길게 있다. (세로 위치는 안중요함)

이 때 한 지점에서 화살을 세로로 날리면 그 지점에 겹쳐있는 풍선들은 모두 터진다.

이 때 모든 풍선을 터트리는 가장 적은 화살을 날리는 횟수를 구하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

정렬을 한 이후에 그리디로 문제를 풀면 될 것 같았다.

(가장 길이가 짧은 풍선이 맨 앞에 있다고 생각하면 쨋든 이 풍선들을 터뜨리긴 해야하니깐 이런 애들부터 터뜨린다라고 생각하면 조금 이해가 쉬우려나..?)

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> a[0] == b[0] ? (a[1] < b[1] ? -1 : 1) : (a[0] < b[0] ? -1 : 1));
        int result = 1, left = points[0][0], right = points[0][1];
        
        for(int i = 1; i < points.length; i++) {
            var p = points[i];
            if(right < p[0]) {
                result++;
                right = p[1];
            } else {
                left = p[0];
                right = Math.min(p[1], right);
            }
        }
        
        return result;
    }
}

---

제출 화면

이야 오늘 진짜 처음보는 경우가 있었는데 정렬 함수 사용할 때는 조심해야한다는 것이다.

아무 생각없이 람다로 (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]를 넘겼는데 여기서 - 연산 때문에 오버플로우가 날 수 있었다.

그래서 정렬을 했는데 정렬이 안되는 기이한 현상이 일어났다... ㅋㅋㅋㅋㅋㅋ

와 진짜 처음보는 경우라서 머리속에는 깊게 남을 것 같다 ㅋㅋㅋ

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.