[백준/c++] 1966번: 프린터 큐

 

 

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

우선순위 큐를 사용해야 하는 문제!

우선순위가 가장 크다는 것을 확인해야 하므로 priority_queue를 사용한다.

- 가장 앞에 있는 문서의 중요도를 확인한다.
- 나머지 문서 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 queue의 가장 뒤에 재배치. 아니면 바로 인쇄

queue에 문서의 Index와 priority value를 넣어준다. 그리고 이제 맨 앞에 있는 문서를 확인해줘야 하는데,

 

- 우선순위가 제일 높다면 (즉, 우선순위 큐의 맨 앞의 원소와 해당 문서의 우선순위가 같다면)

  : 몇번째인지 카운팅하고 이 문서의 index(문서의 번호)와 몇 번째로 인쇄되는지 궁금한 문서의 번호가 동일한지 확인하고

    만약 맞다면 cnt을 출력하고 끝내준다. 

 

- 우선순위가 제일 높지 않다면 

  : 맨 뒤에 넣어준다

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        int cnt = 0;
        queue<pair<int, int>> doc; //index, prio
        priority_queue<int> pq;
        cin >> n >> m;
        for(int i=0; i<n; i++) {
            int a;
            cin >> a;
            doc.push({i, a});
            pq.push(a);
        }
        
        while(!doc.empty()){
            int index = doc.front().first;
            int value = doc.front().second;
            doc.pop();
            if(pq.top() == value){ //doc 맨 앞에 있는 문서의 우선순위가 가장 높은거라면
                pq.pop();
                cnt++; //몇번째인지 카운팅
                if(index == m){ //이 문서의 번호와 몇번째로 인쇄되는지 궁금한 문서 번호가 동일하다면
                    cout << cnt << '\n';
                    break;
                }
            }else{
                doc.push({index, value}); //우선순위가 가장 높지 않으므로 뒤에 넣어준다
            }
        }
    }
    return 0;
}