[Programmers] 요격 시스템(Lv.2)(C++)

풀이 소요시간 : 20분

방금 전에 호텔 대실 이라는 비슷한 문제를 풀어서 그런지 금방 풀 수 있었다. 이번에도 우선순위 큐를 활용한 스케쥴링으로 문제를 풀었는데, 이번에는 우선순위 큐를 굳이 사용하지 않는 간결한 코드를 발견해서 두 가지 방식으로 풀어보도록 하겠다.

시작 범위를 기준으로 오름차순 정렬하였다. 그리고 끝 범위를 우선순위 큐에 push 했다. 시작 구간이 우선순위 큐의 top 보다 같거나 큰 순간이 오면 미사일 갯수를 증가시키고 우선순위 큐를 비어놓는다.

여기서 차밍포인트는 같거나 크다는거다. 문제에 개구간 요격 조건이 있기에 정수 구간이 겹쳐도 요격이 가능한 것이다. 이 부분을 놓쳐서 제 값이 나오지 않았다.

전체 코드(우선순위 큐 : 본인 풀이)

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

priority_queue<int, vector<int>, greater<int>> PQ;

bool Cmp(vector<int> A, vector<int> B){
    return A[0] < B[0];
}

int solution(vector<vector<int>> targets) {
    sort(targets.begin(), targets.end(), Cmp);
    
    PQ.push(targets[0][1]);
    int Cnt = 1;
    
    for(int i = 1; i < targets.size(); i++)
    {
        int First = targets[i][0];
        int Last = targets[i][1];
        
        if(PQ.top() <= First)
        {
            Cnt++;
            while(!PQ.empty()) PQ.pop();
            PQ.push(Last);
        }
        else
        {
            PQ.push(Last);
        }
        
    }
    
    return Cnt;
}

전체 코드(우선순위 큐 사용X)

우선순위 큐를 사용하지 않고 now 라는 변수를 사용했다.
now 는 현재 공통 요격되는 미사일들 중 가장 작은 끝구간을 의미한다.
now 보다 크거나 같은 시작 구간이 들어오면 now 값을 해당 값으로 갱신한다.
그렇지 않는다면 현재 미사일까지 포함해서 가장 작은 끝구간으로 now 값을 갱신 시도한다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

bool Cmp(vector<int> A, vector<int> B){
    return A[0] < B[0];
}

int solution(vector<vector<int>> targets) {
    sort(targets.begin(), targets.end(), Cmp);
    
    //now : 현재 공통 요격 미사일 중 가장 작은 끝 구간
    int now = targets[0][1];
    int Cnt = 1;
    
    for(int i = 1; i < targets.size(); i++)
    {
        int First = targets[i][0];
        int Last = targets[i][1];
        
        if(now <= First)
        {
            Cnt++;
            now = Last;
        }
        else
        {
            now = min(Last, now);
        }
        
    }
    
    return Cnt;
}