[leetcode] Minimum Number of Arrows to Burst Balloons

문제 설명

• 문제 링크
• 풍선들이 xy 좌표에 놓여있다. 모든 풍선의 x 구간을 나타내는 points가 주어진다. points[i] = [x_start, x_end]로 나타낼 수 있다. 그리고 화살을 쏘게 되는데, 화살은 x 좌표 위에서 y 좌표가 증가하는 방향으로 수직 발사한다. 화살을 발사하여 특정 x 좌표에 속한 풍선들을 모두 터뜨릴 수 있다. points를 바탕으로 화살을 쏴서 풍선을 터뜨릴 때, 모든 풍선을 터뜨리는 가장 적은 화살 개수를 구해야 한다.
• 제약 조건
  • 화살 개수 제한 없음
  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= x_start < x_end <= 2^31 - 1

풀이

풀기 전

• 제약 조건에 있는 x의 범위를 보는 순간 좌표를 순회할 순 없겠구나 생각했다. points가 정렬되어 있지 않기 때문에 정렬하면 좋을 거 같았는데, 제약 조건에 points의 길이를 봤을 때 정렬을 해봄직할 거 같았다.
• points를 정렬했을 때, 현재 풍선 구간과 다음 풍선 구간과의 관계를 고민했다. 두 풍선이 함께 터질 수 있다는 건 현재 구간의 end가 다음 구간의 start 보다 크거나 같다는 의미이다. 그래서 points[i+1].start <= points[i].end로 함께 터지는지 체크할 수 있다. 그렇다면 다다음 풍선 구간까지 같이 터뜨릴 수 있는지는 어떻게 알 수 있을까. 현재 구간과 다음 구간의 end 중에서 작은 값이 다다음 구간의 start 보다 크거나 같은지로 체크할 수 있다. points[i+2].start <= min(points[i].end, points[i+1].end)로 체크할 수 있다.
• 위 아이디어가 greedy 한지도 확인해야 한다. 즉, 앞에서부터 순회하면서 조건을 체크할 때 최적의 값이 나오는지 확인해야 한다. 여러 그림을 그려서 확인해봤을 때는 항상 greedy 하게 작동하는 거 같았다. 생각해보면 함께 터뜨릴 수 있는 풍선은 무조건 함께 터뜨리는 게 이득이다. 함께 터뜨리지 않아도 화살 하나는 써야하기 때문이다.

코드

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int ans = 0;

		// 정렬해준다.
        // N=points.size()일 때, 시간복잡도는 O(NlogN)
        sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
            return a[0] <= b[0];
        });

		// 첫 구간의 end를 함께 터뜨릴 수 있는 풍선의 마지노선 구간으로 정한다.
        int limit = points[0][1];
        for (int i=1; i<points.size(); i++) {
        	// 함께 터뜨릴 수 있는 풍선인지 체크한다.
            if (points[i][0] <= limit) {
            	// limit을 갱신한다.
                // 함께 터뜨릴 풍선의 end와 현재 마지노선 중 작은 값을 넣어준다.
                limit = min(limit, points[i][1]);
                continue;
            }
            
            // 함께 터뜨리지 못하는 경우 실행된다.
            // 화살 +1 해주고, limit을 갱신해준다.
            ans++;
            limit = points[i][1];
        }
        ans++;  // 마지막 구간은 for 문에서 체크되지 못하므로 추가해준다.

        return ans;
    }
};

푼 후

• 처음에 limit을 갱신해주지 않아서 틀렸었다.
• 통과됐을 때 runtime이 2초나 걸렸었다. 속도가 하위 7%여서 놀랬다. 정렬 안하는 더 빠른 방법이 있나? 싶어서 다른 사람들이 푼 걸 확인해봤다. 그런데 방식에는 차이가 없었다. 차이는 정렬하는 함수에 있었다. 나는 함수를 정의해서 sort에 넣어줬는데, 다른 사람들은 lambda를 써서 넣고 있었다. 차이가 있나 싶어서 나도 lambda로 넣고 해봤는데 속도가 상위 3%로 올랐다. 왜 이렇게 다른지 아직은 잘 모르겠는데 나중에 찾아봐야겠다.