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 중 최솟값으로 갱신해줘야한다.
'Leetcode' 카테고리의 다른 글
[Leetcode] 71. Simplify Path - JS (0) | 2024.10.29 |
---|---|
[Leetcode] 20. Valid Parentheses - JS (0) | 2024.10.28 |
[Leetcode] 57. Insert Interval - JS (1) | 2024.10.26 |
[Leetcode] 56. Merge Intervals - JS (0) | 2024.10.25 |
[Leetcode] 228. Summary Ranges - JS (0) | 2024.10.24 |