[Programmers, C++]#Level3_단속카메라, 우선순위 큐

#1. 문제

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

 

---

 

#2. 풀이

 

1. 우선순위 큐

[자료구조]#7_우선순위 큐

우선순위 큐는 각 항목에 우선순위를 부여하고, 우선순위가 가장 높은 항목이 먼저 제거되는 특징을 갖습니다. 일반적으로, 우선순위 큐는 힙 자료구조를 통해 구현되며, 내부적으로 반 정렬된 상태를 유지하는 것이 특징입니다.

 

2. 진출 시점을 기준으로 최소 힙을 구성하고, 최소 진출 시점과 현재 진입 시점 비교

1. 먼저, 입력으로 주어진 각 차의 진입 시점과 진출 시점을 pair<진출 시점, 진입 시점>으로 구성하고, 이를 '최소 힙' priority_queue 컨테이너에 삽입해줍니다.
2. 우선순위 큐를 순회하며, 최소 진출 시점을 갖는 차의 진입 시점과 최소 진입 시점을 비교하고, 최소 진입 시점보다 현재 차의 진입 시점이 더 크다면, 단속 카메라 갯수를 1개 추가하고 최소 진입 시점을 현재 차의 진입 시점으로 업데이트 해줍니다.
3. 위 작업을 반복하고, 최종 단속 카메라 갯수를 반환해줍니다.

 

---

 

#3. 코드

/*
    @문제: 모든 차량이 최소 한 번 단속 카메라를 만나도록 하기 위해 필요한 최소 카메라 수
    @설명
        1. pair< 진출 시점, 진입 시점 > 형식, 진출 시점 기준 최소 힙 구성(오름차순)
        2. 최소 진출 시점 > 현재 진입 시점 일 경우, 카메라 한 대 추가적으로 필요 + 최소 진출 시점을 현재 진출 시점으로 업데이트
*/

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

using namespace std;

int solution(vector<vector<int>> routes) {

    int ans = 0;
    // #1. 진출 시점 기준 오름차순 정렬
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    for(int i=0; i<(int)routes.size(); ++i)
    {
        pq.push({routes[i][1], routes[i][0]});
    }

    int minOut = INT_MIN;
    // #2. 최소 카메라 갯수 구하기
    while(!pq.empty())
    {
        int curOut = pq.top().first;
        int curIn = pq.top().second;
        pq.pop();

        // 최소 진출 시점 < 현재 진입 시점 : 카메라 1대 추가, 최소 진출 시점 = 현재 진출 시점
        if(minOut < curIn)
        {
            ans++;
            minOut = curOut;
        }
    }

    return ans;
}

 

---