본문 바로가기
알고리즘 문제/Leetcode

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

by 햄과함께 2022. 1. 13.
320x100

문제 : https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/


points 배열을 start 기준 오름차순, start가 동일한 경우 end 기준으로 오름차순 정렬한다.

points 배열을 앞에서부터 탐색하면서 중복되는 범위를 저장해둔다. (let, duplicate)

duplicate 범위의 start가 end 보다 작아지는 경우 정답을 +1 하고 현재 탐색중인 points 배열 원소값으로 duplicate를 갱신한다.

 

문제의 예제 1번 예시. points = [[10,16],[2,8],[1,6],[7,12]]

[1, 6] x -> [1, 6] 갱신 (정답 + 1)
[2, 8] [2, 6]  
[7, 12] [7, 6] -> [7, 12] 갱신 (정답 + 1)
[10, 16] [10, 12]  

 

시간복잡도는 O(NlogN).


소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/452.%20Minimum%20Number%20of%20Arrows%20to%20Burst%20Balloons.cpp

320x100

댓글