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

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
XY 평면을 나타내는 평평한 벽에 몇 개의 구형 풍선이 테이프로 붙어 있습니다. 
풍선은 2D 정수 배열 점으로 표시됩니다. 
여기서 points[i] = [xstart, xend]는 수평 직경이 xstart와 xend 사이에 걸쳐 있는 풍선을 나타냅니다. 
풍선의 정확한 y 좌표를 모릅니다.

화살표는 x축을 따라 여러 지점에서 수직(양의 y 방향)으로 직접 발사될 수 있습니다. 
xstart 및 xend가 있는 풍선은 xstart <= x <= xend인 경우 x를 향해 발사된 화살에 의해 터집니다. 
쏠 수 있는 화살의 수에는 제한이 없습니다. 
발사된 화살은 계속해서 위로 올라가며 경로에 있는 모든 풍선을 터뜨립니다.

배열 포인트가 주어지면 모든 풍선을 터뜨리기 위해 발사해야 하는 최소 화살 수를 반환합니다.

제한조건
--------------------
- 1 <= points.length <= 10^5
- points[i].length == 2
- -2^31 <= Xstart <= Xend <= 2^31 - 1

 

2. 접근 방법

접근방법
--------------------
우선 start를 기준으로 points를 오름차순 정렬한다.
간격이 겹치지 않는다면 화살을 간격 갯수만큼 쏴야한다.

만약 간격이 겹치면 겹치는 간격에 쏘면 두 간격의 풍선들이 터지므로 
이는 두 간격을 하나로 병합하는 것과 비슷하다.

shoot = 0 초기화
prev = points[0] 초기화

points 배열 1번째부터 순회
병합되는 조건이면 prev[1] 변경

❗️이 때 두 값을 비교하여 최댓값이 아닌 최솟값으로 비교해야한다.
왜냐하면 두 간격이 겹치는 구간 중 화살을 쏴야 두 간격의 풍선이 모두 터지기 때문이다.

병합안되면 prev 갱신하고 shoot++;

 

 

3. 코드

var findMinArrowShots = function(points) {
    points.sort((a,b) => a[0] - b[0]);
    let shoot = 1;
    let prev = points[0];

    for (let i = 1; i < points.length; i++) {
        const point = points[i];
        if (prev[1] >= point[0]) {
            prev[1] = Math.min(prev[1], point[1])
        } else {
            shoot++;
            prev = point
        }
    }
    return shoot;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n logn)

- 공간복잡도: O(1)

 

기존 간격 병합문제에서 약간 꼬아서 낸 문제이다.

화살을 쏴서 두 간격을 모두 맞추려면 겹치는 구간에 쏴야한다.

 

그러므로 누적 병합된 prev는 겹치는 부분을 유지해야만 하므로 end 값을 두 간격의 end 중 최솟값으로 갱신해줘야한다.