우선순위 큐(Priority Queue) 맛보기

우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다.
<위키백과>

데이터를 꺼낼 때, 우선순위가 가장 높은 데이터가 가장 먼저 나온다.
C++ 표준 라이브러리(STL) 컨테이너를 사용하여 우선순위 큐를 활용해 보자!!

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>
class priority_queue

구문은 위와 같으며, Compare 매개변수를 통해 우선순위를 설정할 수 있다.

/* 내림차순 (기본형) */
priority_queue<int, vector<int>, less<int>> pq;
priority_queue<int> pq; 

/* 오름차순 */
priority_queue<int, vector<int>, greater<int>> pq;

1374번: 강의실
https://www.acmicpc.net/problem/1374

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int N, a, b, c, cnt=0;
    cin >> N;
    
    // 강의 시작시간의 오름차순으로 정렬하기 위한 우선순위 큐
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    
    // 강의 종료시간을 오름차순으로 정렬하여 다음 강의의 시작시간과 비교하기 위한 우선순위 큐
    priority_queue<int, vector<int>, greater<int>> pq2;

	// 강의 번호는 사용하지 않고, 시작시간과 종료시간만 우선순위 큐에 삽입
    for(int i=0; i<N; i++) {
        cin >> a >> b >> c;
        pq.push({b, c});
    } 

    for(int i=0; i<N; i++) {
    	// 가장 빨리 끝나는 강의시간보다 다음 강의시작시간이 작다면, 강의실 1개 증가  
        if(i==0 || pq2.top()>pq.top().first){
            cnt++;
            pq2.push(pq.top().second);
            pq.pop();
        }
        // 가장 빨리 끝나는 강의시간보다 다음 강의시작시간이 크거나 같다면 강의실을 늘리지 않아도 됨
        else {
            pq2.push(pq.top().second);
            pq.pop();
            pq2.pop();
        }
    }
	// 최소 강의실 개수 출력
    cout << cnt;
    return 0;
}

다음에는 비교함수를 직접 선언하여 우선순위 큐에 적용해 보자!!