[프로그래머스 Level2] 프린터

📝 프린터

문제 설명

프린터

해결 방법

우선순위 큐와 pair 큐를 활용한다.
우선순위 큐는 삽입 시 우선순위가 높은 순서대로 원소가 정렬된다. (가장 우선순위가 높은 원소가 top에 위치한다.)
우선순위 큐의 top에 있는 원소와 pair 큐에 삽입된 imp(중요도)를 비교해서 전자가 더 크면 인쇄 대기 우선순위가 밀리는 것이므로 pair 큐의 맨 뒤로 보낸다.
그렇지 않다면, 우선순위가 가장 높다는 의미이므로 우선순위 큐와 pair 큐 모두 pop 하고(인쇄), 요청한 문서가 몇번째로 인쇄되는지 알아야 하므로 answer++ 한다.
location(인쇄를 요청한 문서 순서)와 idx(큐에 삽입된 문서 순서)이 같으면 break 한다.

💻소스코드

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    priority_queue<int> pq;
    queue<pair<int, int>> q;
    // 우선순위 큐에 중요도 삽입, pair 큐에 순서와 중요도 삽입
    for (int i = 0; i < priorities.size(); i++) {
        pq.push(priorities[i]);
        q.push({i, priorities[i]});
    }
    
    while (!q.empty()) {
        int idx = q.front().first;
        int imp = q.front().second;
        
        // 인쇄 대기목록에서 imp보다 중요도가 높은 문서가 존재하면 대기목록의 가장 마지막에 넣는다.
        if (pq.top() > imp) {
            q.push(q.front());
            q.pop();
        }
        // 그렇지 않으면 인쇄
        else {
            pq.pop();
            q.pop();
            answer++;
            if (location == idx)    // 인쇄를 요청한 문서가 나오면
                break;
        }
    }
    
    return answer;
}