Leetcode 452. Minimum Number of Arrows to Burst Balloons

문제

문제 링크

풍선이 가로로 차지하는 첫 지점과 끝지점들의 배열이 주어지는데, 이들을 화살로 터뜨린다고 할때 최소한의 화살로 터뜨릴 경우
화살을 몇개나 쓰는가?

예시

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- 6 지점에 쏘면 2,8 과 1,6 이 터진다.
- 11 지점에 쏘면 10, 16 과 7, 12 이 터진다.

제한

• $1 <= points.length <= 10^5$
• $points[i].length == 2$
• $-2^{31} <= x_{start} < x_{end} <= 2^{31} - 1$

풀이

• 어렵게 보일수 있으나, Greedy하게 접근해서 풀수 있다.
• 최대한 풍선의 오른쪽 끝점에서 터뜨린다.

1. 풍선의 집합을 끝나는 지점을 기준으로 정렬한다.
   • 이러면 특정 풍선을 언제까지만 터뜨릴수 있는지를 알수 있다.
2. 첫번째 풍선의 끝점을 저장한다.
   • 만약 이 풍선의 끝점보다 첫 점이 앞선 풍선이 있으면 이 풍선은 그 지점부터는 터뜨릴수 없기에 그때 바로 터뜨려야 한다.
3. 다음 풍선부터 for loop를 돌려 첫 지점이 더 앞서있으면 화살을 앞에서 쐈다고 가정하고 화살갯수를 늘리고 마지막 지점을 새로이 한다.

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda a: a[1])

        last_point = points[0][1]
        arrow = 1
        
        for i in range(1, len(points)):
            if points[i][0] > last_point:
                last_point = points[i][1]
                arrow += 1
        
        return arrow