Level 3. 단속카메라

Level 3. 단속카메라

 

 

여러 개의 구간이 주어진 문제라면, 일단 시작점을 기준으로 정렬할 생각부터 해야 한다.

• 이 문제에서는 최소힙을 구성하기 위해 Section의 < 연산자를 반대로 오버로딩했다.
  set, map 등과 달리 우선순위 큐는 최대힙이 기본이기 때문이다.
• 별도 관리하는 끝점과 각 구간의 시작점을 비교하므로, 끝점은 정렬하지 않아도 된다.

 

현재 단속 카메라를 배치할 수 있는 끝점을 end 변수로 관리하고, end보다 큰 시작점이 나오면 새로운 카메라를 배치해야 한다.

• end보다 작거나 같은 시작점이 나오면 현재 카메라를 공유할 수 있다는 뜻인데, 이 때도 가능한 작은 위치에 카메라를 배치해 더 많은 카메라를 공유할 수 있도록 갱신해야 한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Section
{
    int start;
    int end;

    friend bool operator < (const Section& A, const Section& B) { return A.start > B.start; }
};

int solution(vector<vector<int>> routes)
{
    int answer = 0;
    int end = -30'001;
    priority_queue<Section> prQue;

    for (vector<int>& rt : routes)
        prQue.push({rt[0], rt[1]});

    while (!prQue.empty())
    {
        Section sec = prQue.top(); prQue.pop();

        if (end < sec.start)
            end = sec.end,
            ++answer;
        else
            end = min(end, sec.end);
    }

    return answer;
}

 

우선순위 큐에서 pop() 연산밖에 하지 않으므로, 굳이 큐를 쓰지 않고 단순히 정렬해서 해결해도 된다.

• vector는 비교 연산자를 지원한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> routes)
{
    int answer = 0;
    int end = -30'001;

    sort(routes.begin(), routes.end());

    for (vector<int>& rt : routes)
    {
        if (end < rt[0])
            end = rt[1],
            ++answer;
        else
            end = min(end, rt[1]);
    }

    return answer;
}