[프로그래머스] 프린터 (C++)

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int,int> > q;
    priority_queue<int> pq;
    for (int i=0; i<priorities.size(); i++){
        q.push({priorities[i], i});
        pq.push(priorities[i]);
    }
    while (!q.empty()){
        int doc=q.front().first;
        int num=q.front().second;
        q.pop();
        if (doc==pq.top()){
            answer++;
            pq.pop();
            if (num==location)
                break;
        }
        else{
            q.push({doc,num});
        }
    }
    return answer;
}

자료구조 2개를 둔다.

하나는 프린터 역할을 할 큐.

다른 하나는 최대값을 뽑아내기 위한 우선순위 큐.

 

우선순위 큐의 top은 현재 있는 것에서 가장 큰 애가 나오게되므로,

프린터 역할을 하는 큐에서 그 큰 애가 나올 때까지 뽑고+뒤로 다시 붙여준다.

큰애가 나오면 우선순위 큐에 있는 가장 큰 애를 뽑고, 순서를 카운트한다.

location의 인덱스가 현재 프린터에서 나온 애와 동일하다면, 반복문을 탈출한다.