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

문제

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons. Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path. Given the array points, return the minimum number of arrows that must be shot to burst all balloons.


좌표평면에 풍선이 존재하며 풍선들의 xStart, xEnd좌표가 저장되어있는 points 2차원 배열이 주어집니다.
아래에서 위로 화살을 쏴서 풍선을 터트릴 때, 풍선을 모두 터뜨릴 수 있는 화살의 최소 개수를 구하시오.

예시

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].

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

 

풀이

먼저, 풍선을 터뜨릴 때 동시에 터뜨릴 수 있는 조건을 찾아야 합니다.

[[10,16],[2,8],[1,6],[7,12]]

[1,6]과 [2,8] 은 화살 하나로 동시에 터뜨릴 수 있습니다.

좌표를 보시면 첫번째 풍선의 end좌표인 6이 두번째 풍선의 start좌표인 2보다 크죠?

즉, end좌표가 다른풍선의 start좌표보다 큰 경우 동시에 터뜨릴 수 있다는 뜻입니다.

 

위 방법을 이용해서 그리디 알고리즘을 사용하여 이 문제를 쉽게 해결할 수 있습니다.

먼저 그리디 알고리즘을 사용하려면 우선 정렬을 해야합니다.

end 좌표를 작은 순서대로 정렬을 해줘야 배열을 순회하며 순차적으로 해결하기 쉽기 때문입니다.

 

코드

class Solution(object):
    def findMinArrowShots(self, points):
        arrow = 1
        points = sorted(points, key = lambda x:x[1])
        last = points[0][1]
        for i in range(1, len(points)):
            if(last < points[i][0]):
                arrow += 1
                last = points[i][1]


        return arrow

 

비교 기준이 되는 end 좌표를 저장하고 있는 last변수를 사용하였습니다.

배열을 순회하며 end좌표가 start 좌표보다 작은경우, 동시에 터뜨릴 수 없기 때문에 화살 개수를 추가해줍니다.

화살을 1로 초기화 한 이유는, 마지막 풍선의 경우 비교할 대상이 없기 때문입니다.

 

복잡도

• 시간 복잡도: O(nlogn) 
• 공간 복잡도: O(1)