[Interval][Medium] 452. Minimum Number of Arrows to Burst Balloons

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 input을 풍선의 직선에서의 좌표라고 가정한다. 

 이때 풍선을 모두 떠뜨릴 수 있는 화살의 수를 구하라. 

 겹쳐진 풍선은 모두 한번에 떠뜨릴 수 있다. 

 

Solution. 

 이전 문제와 유사한 문제다. 

 다만, 어느 경우에 기본 조건을 갱신할 것인가 등이 조금 다르다. 

 

 먼저 직전 문제와 같이 시작 지점을 기준으로 input정렬이 필요하다. 

 이후에 이전 끝 부분이 현재의 시작부분과 같이 터질 수 있는 조건이 되면,

 즉, 겹쳐진 풍선이라고 간주 된다면, 끝 지점을 더 작은 것으로 갱신한다. 그래야 다음 것이 이 겹쳐진 풍선들에 다시 또 겹쳐질 수 있는지 판단 가능하게 된다. 

  

  즉, 겹쳐진 풍선이라면, 더 작은 풍선으로 size 갱신한다. 이때 화살 수는 늘지 않는다.

  겹쳐지지 않았다면, 여지껏 던진 화살수에 1을 더하고, 새 풍선의 끝으로 size를 갱신하고 로직을 다시 시작한다.

 

  로직을 코드로 써 보자. 

 

static bool arrow_sort(vector<int>& v1, vector<int>& v2)
{
    return v1[0] < v2[0];
}
int findMinArrowShots(vector<vector<int>>& points) 
{
    if (points.size() <= 1)
        return points.size();

    // sort.
    sort(points.begin(), points.end(), arrow_sort);

    int cntArrow = 0;
    int lastEnd = points[0][1];
    for (int k = 1; k < points.size(); ++k)
    {
        // 공통으로 터뜨릴수 있는 풍선이면, 더 작은 끝으로 갱신. 
        if(lastEnd >= points[k][0])
            lastEnd = min(lastEnd, points[k][1]);

        // 공통으로 터뜨릴수 없으면 정리하고, 끝을 update.
        else
        {
            ++cntArrow;
            lastEnd = points[k][1];
        }
    }
    ++cntArrow;
    return cntArrow;
}

 

 

결과.