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

문제 요약

• 알고리즘 분류:  그리디, 정렬
• 난이도: Medium
• 문제내용:
  • .벽에 붙어있는 풍선들은 [xstart, xend] 형태로 주어지며, x축에서 수직으로 화살을 쏴 터뜨릴 수 있습니다.
  • 한 번 발사된 화살은 무한히 위로 이동하며 경로 내 모든 풍선을 터뜨립니다. 모든 풍선을 터뜨리는 데 필요한 최소 화살 개수를 구하세요.
• 사이트 주소: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/

문제풀이

이번 문제는 완전탐색으로 풀면 O(N^2)나오지만 그러면 시간 초과가 나서 O(N^2)안되는 방법으로 끝내야 한다. 그래서 그리디로 간단하게 풀것이다. 그리디 관련 내용은 아래글로 참고 하면된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근 방법

 그리디문제는 구현보다 아이디어가 요구하는 문제이다. 그래서 어떻게 접근 하면 좋을지 보면 된다. 일단 아래 예제로 보자

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

위 예제를 그림으로 나타 내면 아래와 같다.

 여기서 아래 그림을 x축 기준으로 정렬 하면 아래와 같다.

 여기서 첫번째 끝 지점에서 화살을 쏘고 그 다음에는 첫번째 화살 벗어난 기점 풍선에서 쏘면 된다. 그러면 아래 그림 처럼 두번 쏘게 된다. 

 그럼 여기서 더 나아가보면 두번째 화살 기점에서 벗어난 첫번째 풍선의 끝지점 쏘면 그 다음 화살에서 벗어난 풍선에서 끝지점에서 화살을 쏘는 식으로 하면 된다. 

 다시 정리하면 아래와 같다.

1. X축 과 풍선 끝 지점 기준으로 정렬한다.
2. 첫번째 화살은 정렬한 points에서 0번째 인덱스 끝지점 값으로 지정한다.
3. 1번째 인덱스 부터 탐색해서 만약에 i번째 인덱스에서 첫 지점보다 작으면 화살 개수 한개 추가하고 i번째 인덱스 끝지점으로 화살 지정한다.

위와 같이 구현하면 시간 복잡도는 정렬때문에 O(NlogN)만큼 나온다.

Code

Python

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        
        size = len(points)
        points.sort(key=lambda point: point[1]) # 끝 지점으로 정렬

        count = 1
        arrow = points[0][1]
        for i in range(1, size):
            # 끝 지점이 시작 지점 작을때
            if arrow < points[i][0]:
                count += 1 # 개수 증가
                arrow = points[i][1] # 다시 끝지점으로 위치 설정

        return count

Java

class Solution {
    public int findMinArrowShots(int[][] points) {
        int size = points.length;

        // 끝 지점으로 정렬
        Arrays.sort(points, Comparator.comparingInt(point -> point[1]));

        int count = 1;
        int arrow = points[0][1];
        for (int i = 1; i < size; i++) {
            // 끝 지점이 시작 지점 작을때
            if(arrow < points[i][0]){
                count++; // 개수 증가
                arrow = points[i][1]; // 다시 끝지점으로 위치 지정
            }
        }

        return count;
    }
}

Javascript

var findMinArrowShots = function(points) {
    const size = points.length;

    // 끝 지점으로 정렬
    points.sort(function(point1, point2) {
        return point1[1] - point2[1];
    })

    let count = 1;
    let arrow = points[0][1]; // 끝 지점으로 정렬

    for (let i = 0; i < size; i++) {
        if(arrow < points[i][0]){
            count++; // 개수 증가
            arrow = points[i][1]; // 다시 끝지점으로 위치 지정
        }
    }

    return count
};