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

LeetCode/공통

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

hyunkookim 2024. 11. 10. 15:10

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.

Example 1:

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

Example 2:

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.

Example 3:

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

Constraints:

1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

문제 해설

이 문제는 XY 평면의 x축 위에 놓인 풍선들을 최소한의 화살로 터뜨리는 방법을 구하는 문제입니다. 풍선들은 각자의 x축에서 시작점과 끝점을 가지며, 화살은 x축의 특정 위치에서 수직으로 발사됩니다. 풍선을 터뜨리려면 화살의 x축 위치가 풍선의 시작점과 끝점 사이에 있어야 합니다.

문제의 세부 사항

입력 설명:
- points는 풍선의 x축 범위를 나타내는 2차원 배열입니다.
- points[i] = [xstart, xend]는 풍선의 x축에서 시작점 xstart와 끝점 xend를 나타냅니다.
화살 발사 규칙:
- 화살은 x축의 특정 위치에서 발사되며, **y축 양의 방향(위쪽)**으로 무한히 날아갑니다.
- 화살의 x축 위치가 xstart <= x <= xend에 해당하면 해당 풍선은 터집니다.
- 화살 하나로 여러 풍선을 터뜨릴 수 있습니다.
목표:
- 모든 풍선을 터뜨리기 위해 필요한 최소한의 화살 수를 계산합니다.

문제 풀이 접근법

정렬: 풍선의 끝점(xend)을 기준으로 정렬합니다.
- 왜 끝점을 기준으로 정렬하나요?
  - 끝점 기준으로 정렬하면 가장 왼쪽에서 터질 수 있는 풍선을 한 번의 화살로 터뜨릴 가능성이 높아집니다.
겹치는 범위 확인:
- 첫 번째 풍선부터 시작하여 화살을 쏘고, 화살이 터뜨릴 수 있는 모든 풍선을 확인합니다.
- 현재 화살로 터뜨릴 수 없는 풍선이 나타나면 새로운 화살을 추가로 발사합니다.
결과 반환: 필요한 화살의 개수를 반환합니다.

제약 조건

풍선의 개수: 1 <= points.length <= 10^5 (최대 100,000개 풍선)
x축 범위: -2^31 <= xstart < xend <= 2^31 - 1 (32비트 정수)

효율적인 풀이가 필요하며, 정렬과 한 번의 순회로 해결 가능한 O(nlog⁡n) 알고리즘이 적합합니다.

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # Step 1: 입력된 풍선 리스트가 비어 있으면 화살이 필요하지 않음
        if not points:
            return 0  # 풍선이 없으므로 필요한 화살 개수는 0

        # Step 2: 풍선을 끝나는 시간(xend) 기준으로 정렬
        # 정렬 이유:
        # - 끝나는 시간이 빠른 풍선을 먼저 처리하면 이후 겹치는 풍선을 효율적으로 터뜨릴 수 있음
        # 예제: points = [[10,16],[2,8],[1,6],[7,12]] → [[1,6],[2,8],[7,12],[10,16]]
        points.sort(key=lambda x: x[1])

        # Step 3: 초기화
        # arrows: 최소 한 발의 화살은 필요하므로 초기값을 1로 설정
        # prev_end: 첫 번째 화살은 첫 번째 풍선의 끝점에 맞춰 발사
        arrows = 1
        prev_end = points[0][1]  # 첫 번째 풍선의 끝점은 6 (정렬된 첫 번째 풍선: [1,6])

        # Example simulation starts here
        # 풍선 리스트 (정렬된 상태): [[1,6],[2,8],[7,12],[10,16]]
        # 현재 상태: 화살 개수 arrows = 1, 마지막 화살 위치 prev_end = 6

        # Step 4: 풍선 리스트를 순회하며 화살이 필요할 때마다 추가
        for start, end in points[1:]:
            # 현재 풍선: [2,8]
            # start = 2, end = 8
            # 2 <= prev_end (6) → 기존 화살로 터짐 → 화살 추가하지 않음

            # 다음 풍선: [7,12]
            # start = 7, end = 12
            # 7 > prev_end (6) → 새로운 화살 필요
            if start > prev_end:
                arrows += 1  # 화살 개수 증가: arrows = 2
                prev_end = end  # 새로운 화살의 위치를 현재 풍선의 끝점(12)으로 설정

            # 다음 풍선: [10,16]
            # start = 10, end = 16
            # 10 <= prev_end (12) → 기존 화살로 터짐 → 화살 추가하지 않음

        # 최종 상태: 화살 개수 arrows = 2 (필요한 최소 화살 개수)

        # Step 5: 필요한 최소 화살 개수를 반환
        return arrows

왜 arrows를 1로 초기화하는가?

왜 오버랩 체크에서 arrows를 1 추가만 하고 빼지 않는가?

요약

arrows = 1로 시작하는 이유:
- 적어도 하나의 화살은 반드시 필요합니다(첫 번째 풍선을 처리하기 위해).
겹칠 때 arrows를 빼지 않는 이유:
- 겹침은 추가 화살이 필요 없다는 뜻일 뿐, 이미 사용된 화살의 개수를 줄일 필요는 없습니다.
- 새로운 화살이 필요할 때만 arrows를 증가시키면 됩니다.

https://youtu.be/lPmkKnvNPrw?si=RrLpwsFg6dN2XRru

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # Step 1: 입력된 풍선 리스트를 시작점(xstart) 기준으로 정렬
        # 정렬 이유:
        # - 시작점 기준으로 정렬하면 순서대로 겹치는 구간을 처리하기 편리함.
        points.sort()

        # Step 2: 초기화
        # res: 최대 화살 개수로 초기화 (모든 풍선이 겹치지 않는 경우, 풍선 개수만큼 화살이 필요)
        res = len(points)  
        # prev: 이전 풍선의 범위를 저장. 초기값으로 첫 번째 풍선 설정
        prev = points[0]

        # Step 3: 두 번째 풍선부터 순회하며 겹치는지 확인
        for i in range(1, len(points)):
            curr = points[i]  # 현재 풍선의 범위를 curr에 저장
            
            if curr[0] <= prev[1]:  # 현재 풍선의 시작점이 이전 풍선의 끝점 이하인 경우 (겹침)
                res -= 1  # 겹치므로 추가 화살이 필요 없음 → 화살 개수를 1 감소
                
                # 겹치는 구간을 계산하여 prev를 업데이트
                # 겹치는 구간의 시작점은 curr[0]
                # 겹치는 구간의 끝점은 두 풍선의 끝점 중 더 작은 값
                # case:
                # [1, 5], [2, 6] -> overlapping [2, 5]
                # [1, 5], [2, 4] -> overlapping [2, 4]
                prev = [curr[0], min(curr[1], prev[1])]  # 겹치는 구간으로 업데이트
            else:  # 겹치지 않는 경우
                prev = curr  # 현재 풍선으로 prev를 업데이트 
				# (새로운 화살 필요, 제거 하지않음, res 그대로 둠)
        
        # Step 4: 필요한 최소 화살 개수를 반환
        return res

이 코드는 화살 개수를 최대값(len(points))으로 초기화하고, 겹치는 풍선마다 화살 개수를 줄이는 방식으로 동작합니다.
결과적으로 필요한 최소 화살 개수를 반환합니다.

두번째 시도

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # end 기준으로 정렬
        points.sort(key=lambda x : x[1])

        overlap_cnt = 0
        prev_end = -float("inf")

        for start, end in points:
            if prev_end < start: # 안겹치는 구간
                prev_end = end
            else: # 겹치는 구간
                overlap_cnt += 1

        # 총 필요한 화살 수: 전체 풍선 수 - 겹치는 풍선 수
        return len(points) - overlap_cnt

또는

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0

        # 끝점을 기준으로 정렬
        points.sort(key=lambda x: x[1])

        # 첫 번째 화살 설정
        arrows_cnt = 1
        prev_end = points[0][1]

        for start, end in points:
            if start > prev_end:  # 겹치지 않는 구간 발견
                arrows_cnt += 1       # 새로운 화살 필요
                prev_end = end    # 화살의 끝점 갱신

        return arrows_cnt

세번째

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # Step 1: 입력된 풍선 리스트를 시작점(xstart) 기준으로 정렬
        # 정렬 이유:
        # - 시작점 기준으로 정렬하면 순서대로 겹치는 구간을 처리하기 편리함.
        points.sort()

        # Step 2: 초기화
        # res: 최대 화살 개수로 초기화 (모든 풍선이 겹치지 않는 경우, 풍선 개수만큼 화살이 필요)
        res = len(points)  
        # prev: 이전 풍선의 범위를 저장. 초기값으로 첫 번째 풍선 설정
        prev = points[0]

        # Step 3: 두 번째 풍선부터 순회하며 겹치는지 확인
        for i in range(1, len(points)):
            curr = points[i]  # 현재 풍선의 범위를 curr에 저장
            
            if curr[0] <= prev[1]:  # 현재 풍선의 시작점이 이전 풍선의 끝점 이하인 경우 (겹침)
                res -= 1  # 겹치므로 추가 화살이 필요 없음 → 화살 개수를 1 감소
                
                # 겹치는 구간을 계산하여 prev를 업데이트
                # 겹치는 구간의 시작점은 curr[0]
                # 겹치는 구간의 끝점은 두 풍선의 끝점 중 더 작은 값
                # case:
                # [1, 5], [2, 6] -> overlapping [2, 5]
                # [1, 5], [2, 4] -> overlapping [2, 4]
                prev = [curr[0], min(curr[1], prev[1])]  # 겹치는 구간으로 업데이트
            else:  # 겹치지 않는 경우
                prev = curr  # 현재 풍선으로 prev를 업데이트 
				# (새로운 화살 필요, 제거 하지않음, res 그대로 둠)
        
        # Step 4: 필요한 최소 화살 개수를 반환
        return res

겹치는 구간으로 업데이트하는 이유는 최소한의 화살로 모든 풍선을 터뜨리기 위해 겹치는 영역만 추적하기 때문입니다.

문제 이해:

points는 풍선들의 위치를 나타내며, 각 풍선은 [start, end]로 표현됩니다.
목표는 겹치는 구간을 효율적으로 처리하여 최소한의 화살로 모든 풍선을 터뜨리는 것입니다.

겹치는 구간으로 업데이트하는 이유:

겹치는 구간의 핵심: 한 화살로 터뜨릴 수 있는 범위
- 두 구간이 겹친다면, 그 겹치는 구간 안에서 한 번의 화살로 두 풍선을 모두 터뜨릴 수 있습니다.
- 따라서 현재까지 겹친 구간을 유지하고, 새로운 풍선과의 겹침 여부를 확인해 최소화된 겹치는 구간을 업데이트합니다.
prev = [curr[0], min(curr[1], prev[1])]의 의미:
- curr[0]과 prev[1]의 최소값을 유지하여 겹치는 구간의 끝점을 좁힙니다.
- 이렇게 하면 겹치는 구간이 점점 줄어들어, 더 많은 풍선이 새 화살 없이 처리됩니다.

'LeetCode > 공통' 카테고리의 다른 글

[LeetCode 75] Medium - 236. Lowest Common Ancestor of a Binary Tree (0)	2024.11.17
[LeetCode 75] Medium - 11. Container With Most Water ☆ (1)	2024.11.12
[LeetCode 75] Easy - 392. Is Subsequence (0)	2024.11.12
[LeetCode 75] Medium - 208. Implement Trie (Prefix Tree) (2)	2024.11.09
[LeetCode 75] Easy - 136. Single Number (0)	2024.11.09

현재글[LeetCode 75] Medium - 452. Minimum Number of Arrows to Burst Balloons

hyunkookim 님의 블로그

hyunkookim 님의 블로그 입니다.

sorting, LeetCode, dfs, array / string, BST, heap, 우선순위큐, 오블완, dp, 티스토리챌린지, Backtracking, tree, BFS, Coding Test, Graphs, monotonic stack, Two pointers, dp2d, leetcode75, top150,

Today :
Yesterday :

hyunkookim 님의 블로그