[2024] day 79. Leetcode 452. Minimum Number of Arrows to Burst Balloons

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 18일 (월)
Leetcode daily problem

Minimum Number of Arrows to Burst Balloons

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=daily-question&envId=2024-03-18

Problem

[start, end]의 범위를 가진 풍선이 담긴 배열 points가 주어질 때,
모든 풍선을 터트리기 위해 필요한 최소한의 화살 수를 반환한다.

화살표는 x축을 따라 여러 지점에서 수직(양의 y 방향)으로 직접 발사될 수 있고, xstart 및 xend가 있는 풍선은 xstart <= x <= xend인 경우 x를 향해 발사된 화살에 의해 터질 수 있다.

Solution

greedy algorithm

해당 문제는 겹치는 부분을 최대한 많이 포함하는 구간을 찾는 것인데,
겹치는 부분에 여러 풍선을 터트릴 수 있기 때문이다.
그래서 해당 풍선을 먼저 정렬하는 것이 중요하다.
주어진 배열의 원소를 [start,end]라고 했을 때 start를 기준으로 오름차순으로 정렬한 후 첫번째 풍선이 터질 수 있는 범위를 기준으로 설정한다.
그리고 다음 풍선이 터질 수 있는 범위와 현재 설정된 범위가 겹치는지 확인한다.

겹치는 부분이 없다면 화살을 하나 사용하고, 설정된 부분과 겹치는 부분으로 업데이트 한다. 겹치는 부분이 있다면 설정된 범위를 겹치는 부분으로 업데이트 한다.

모든 풍선을 터트릴 때까지 반복하는 그리디 알고리즘을 사용한다.

Code

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[0])
        prev = float('inf')
        ans = 0

        for start, end in points:
            if start > prev :
                ans +=1
                prev = end

            else:
                prev = min(prev, end)
            
        return ans+1
 

Complexicity

시간 복잡도

주어진 배열을 정렬하는 과정에서 O(nlogn)이 소요되고,
각 배열을 한번 탐색하면서 풍선의 범위를 찾고, 필요한 화살을 업데이트하므로 O(n)이 시간이 소요된다.
즉 최종 시간복잡도는 O(nlogn)이다.

공간 복잡도

추가적인 데이터메모리를 사용하지 않고 화살의 수와 기존의 범위만 업데이트하므로, 공간복잡도는 O(1) 이다.