프로그래머스 : 단속카메라

https://programmers.co.kr/learn/courses/30/lessons/42884#

코딩테스트 연습 - 단속카메라

 

먼저 우선순위 큐에 위치 순으로 진입, 진출 이벤트를 분할하여 담아주었습니다.

만약 진입, 진출 위치가 동일하다면, 진입 이벤트에 먼저 우선순위를 두었습니다.

진출 이벤트를 받을 때 카메라를 설치하기 때문에, 겹치는 구간에서 진입한 차량 번호를 먼저 기억해주기 위함입니다.

진출을 방문할 때마다 아직 카메라를 만나지 못한 차량 번호라면 카메라를 설치해주고,

이미 진입해있어서 현재 설치하는 카메라의 단속 범위에 들어온 차량들을 모두 표시해주었습니다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

class compare {
public:
    bool operator()(const pair<int, pair<int, int>>& a, const pair<int, pair<int, int>>& b) {
        if(a.first == b.first) {
            return a.second.first > b.second.first;
        } else {
            return a.first > b.first;
        }
    }  
};

int solution(vector<vector<int>> routes) {
    int answer = 0;
    vector<bool> visit(routes.size(), false); // 단속 카메라 만나는지 여부
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, compare> pq;
    for(int i=0; i<routes.size(); i++) { // 진입, 진출 이벤트 분할해서 pq 삽입
        pq.push({routes[i][0], {0, i}}); // 진입
        pq.push({routes[i][1], {1, i}}); // 진출
    }
    vector<int> enter; // 진입한 차량 번호
    while(!pq.empty()) {
        int first = pq.top().first;
        int second = pq.top().second.first;
        int num = pq.top().second.second;
        pq.pop();
        if(second == 0) { // 진입
            enter.push_back(num);
        } else { // 진출
            if(!visit[num]) {
                for(int i=0; i<enter.size(); i++) { // 단속용 카메라가 만나는 차량들 true
                    visit[enter[i]] = true;
                }
                enter.clear();
                answer++;
            }
        }
    }    
    return answer;
}