C++로 풍선을 터뜨리는 최소 화살 개수 구하기

문제 이해하기

2차원 공간에 여러 개의 구형 풍선이 흩어져 있다고 가정해 봅시다. 각 풍선은 수평 지름의 시작 좌표(xstart)와 끝 좌표(xend)를 가지며, 시작 좌표는 항상 끝 좌표보다 작습니다. 풍선의 개수는 최대 10⁴개입니다.

화살은 x축 위의 임의의 지점에서 정확히 수직 방향으로 발사할 수 있으며, 발사 횟수에는 제한이 없습니다. 또한 한 번 발사된 화살은 무한히 위로 계속 날아간다고 가정합니다. 위치가 xstart부터 xend까지인 풍선은 xstart ≤ x ≤ xend를 만족하는 지점 x에서 발사된 화살에 맞으면 터집니다. 우리가 구해야 할 것은 모든 풍선을 터뜨리기 위해 필요한 최소 화살 개수입니다.

예를 들어 입력이 [[10,16],[2,8],[1,6],[7,12]]라면 출력은 2가 됩니다. x = 6에서 화살을 발사하면 [2,8]과 [1,6] 범위의 풍선이 동시에 터지고, x = 11에서 화살을 한 번 더 발사하면 나머지 풍선들도 모두 터질 수 있습니다.

알고리즘 접근 방식

이 문제는 그리디(Greedy) 알고리즘을 활용한 구간 스케줄링 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 풍선을 끝 좌표 기준으로 정렬한 뒤, 현재 화살이 닿을 수 없는 새로운 풍선을 만날 때만 화살을 추가로 발사하는 것입니다.

두 구간이 겹치는지 판단하는 intersect() 메서드와, 겹치는 풍선들의 범위를 관리하는 manipulate() 메서드를 정의합니다.
풍선 위치 배열 pos를 받아, 끝 좌표(xend)를 기준으로 오름차순 정렬합니다.
n := 풍선 개수이며, n이 0이면 즉시 0을 반환합니다.
currEnd := 정렬 후 첫 번째 풍선의 끝 좌표로 초기화하고, 화살 개수 cnt := 1로 설정합니다.
i를 1부터 n-1까지 반복하면서, 현재 풍선의 시작 좌표가 currEnd보다 크면(즉, 기존 화살이 닿지 않으면) cnt를 1 증가시키고 currEnd를 해당 풍선의 끝 좌표로 갱신합니다.
반복이 끝나면 cnt를 반환합니다.

이 방식의 시간 복잡도는 정렬에 의해 O(n log n)이며, 공간 복잡도는 O(1)입니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 과정을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool intersect(vector<int>& a, vector<int>& b){
      return a[1] >= b[0];
   }
   static bool cmp(vector<int>& a, vector<int>& b){
      return a[1] < b[1];
   }
   void manipulate(vector<int>& a, vector<int>& b){
      a[0] = min(a[0], b[0]);
      a[1] = max(a[1], b[1]);
   }
   int findMinArrowShots(vector<vector<int>>& points) {
      sort(points.begin(), points.end(), cmp);
      int n = points.size();
      if(!n) return 0;
      int currEnd = points[0][1];
      int cnt = 1;
      for(int i = 1; i < n; i++){
         if(currEnd < points[i][0]){
            cnt++;
            currEnd = points[i][1];
         }
      }
      return cnt;
   }
};
main(){
   vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
   Solution ob;
   cout << (ob.findMinArrowShots(v));
}

입력

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