[LeetCode] 452. Minimum Number of Arrows to Burst Balloons - 문제풀이

Description

여러개의 포인터로 이루어진 범위를 풍선이라고 하고 최소 몇개의 화살을 사용해서 풍선을 제거 할 수 있는지 찾는 문제입니다. 예를 들어 Example1에서 {1,6},{2,8}에서 겹치는 범위인 2,3,4,5,6에 화살을 던지면 둘다 제거 할 수 있고 이런 식으로 모든 풍선을 제거할 수 있는 최소한의 개수를 구해주시면 됩니다.

 

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

Solution 1. 탐욕 알고리즘(Greedy Algorithm)

public int findMinArrowShots(int[][] points) {
        
    if(points.length == 1){return 1;} // edge case
    Arrays.sort(points, (o1, o2) -> {
        return Integer.compare(o1[1],o2[1]); // 뒷자리 기준 오름차순.
    });

    int arrows = 1;
    int prev = points[0][1]; // 마지막 끝자리
    for (int i = 1; i < points.length; i++) {
        if( points[i][0] <= prev){ // 이전 마지막이 현재 범위에 있으면 화살 안쓰고 패스
            continue;
        }else{ // 이전 마지막이 포함이 안되면 새로 화살 하나 쓰고 다음 풍선 체크
            arrows++;
            prev = points[i][1];
        }
    }
   return arrows;
}

대부분 이런 문제는 탐욕 알고리즘(Greedy Algorithm)이용하여 풀어냅니다. 그리디 알고리즘 또는 탐욕 알고리즘이란 현재 상황에서 가장 최선의 선택을 해 나가는 알고리즘을 말합니다. 해당 알고리즘이 항상 최적해가 나오는 것은 아니기 때문에 문제를 보시고 최적해가 나올 수 있는 지를 판단하셔야 합니다.

유사한 문제로는 거스름돈 문제, 겹치지 않는 최적의 수강신청, 회의실 예약등의 활동 선택 문제등이 출제됩니다.

Reference

Middle of the Linked List - LeetCode

Middle of the Linked List - LeetCode