Level 2. 요격 시스템

Level 2. 요격 시스템

 

 

Level 3. 단속카메라와 정확히 같은 문제다.

• 새로운 구간으로 넘어갈지 검사할 때 =을 붙이는 것만 다르다.

 

구간이 나온다면 항상 시작점을 기준으로 정렬해 생각하면 된다.

 

두 구간이 겹치는 경우가 대부분이지만, 구간을 완전히 포함하는 경우도 있으므로 끝점을 최솟값으로 갱신해주어야 한다.

 

#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>> targets)
{
    int answer = 0;
    int end = -1;
    priority_queue<Section> prQue;

    for (vector<int>& t : targets)
        prQue.push({t[0], t[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;
}

 

우선순위 큐를 사용하지 않고 미리 정렬해도 된다.

 

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

using namespace std;

int solution(vector<vector<int>> targets)
{
    sort(targets.begin(), targets.end());

    int answer = 1;
    int e = targets.front()[1];

    for (vector<int>& t : targets)
        if (e <= t[0])
            ++answer,
            e = t[1];
        else
            e = min(e, t[1]);

    return answer;
}

 

시작점이 아닌 끝점을 기준으로 정렬하면, 끝점을 최솟값으로 갱신하지 않아도 된다.

• 현재 구간의 끝점은 현재 미사일로 파괴할 수 있는 구간에서 이미 최솟값이기 때문이다.

 

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

using namespace std;

int solution(vector<vector<int>> targets)
{
    sort(targets.begin(), targets.end(), [](auto& t1, auto& t2) { return t1[1] < t2[1]; });

    int answer = 1;
    int e = targets.front()[1];

    for (vector<int>& t : targets)
        if (e <= t[0])
            ++answer,
            e = t[1];

    return answer;
}