[C++] 요격 시스템

[문제]

코딩테스트 연습 - 요격 시스템 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

우선순위 큐를 사용해서 쉽게 풀 수가 있던 문제였다.

1. 첫번째로 sort 알고리즘을 이용해서 targets를 모두 정렬해주자.

2. 오름차순(작은 숫자가 앞에 오는) 우선순위큐를 선언해주자.

3. 우선순위큐에 targets[0]번째의 종료시점을 넣어주자.

4. 처음부터 끝까지 targets를 가면서 만일 targets[i]번째의 시작지점이 우선순위 큐에 넣어져있는 종료시점보다 빠르다면 우선순위큐에 i번째의 종료시간을 넣어주자.

5. 만일 4번의 조건에 만족을 하지 않는다면 우선순위큐 안에 있는 내용을 모두 비워주고 i번째 종료시간을 우선순위큐에 다시 넣어주자. 

6. 만일 5번이 시행된다면 answer을 증가해주자.

 

조건을 만일 세분화 시켜서 많아 보이지만 사실 코드로 보면 생각보다 적게 쉬운 풀이가 가능하다.

[회고]

어떤 알고리즘을 쓸까 고민을 했다가 우선순위 큐를 사용했다. 다만, 다른 사람들의 풀이를 보니 우선순위큐를 사용하지 않았어도 충분히 풀렸을 문제.

[코드]

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

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(),targets.end());
    
    priority_queue<int,vector<int>,greater<int> > pq;
    pq.push(targets[0][1]);
    answer++;
    
    for(int i = 1;i<targets.size();i++){
        if(pq.top() > targets[i][0]){
            pq.push(targets[i][1]);
            continue;
        }
        while(pq.size() > 0){
            pq.pop();
        }
        answer++;
        pq.push(targets[i][1]);
    }
    
    return answer;
}