백준 1966 - 프린트 큐

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

1966번: 프린터 큐

문제 설명

---

 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

 

Rule

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.

2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

 

Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다.

예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

 

 

접근 방식

---

프린트 출력마다 우선순위를 가지고 있기 때문에 결국은 우선순위대로 출력되며 그보다 앞 순위에 있었던 프린트 큐는 뒤로 가게 된다. 따라서 출력되는 우선순위는 같다. 따라서 규칙에 따라 뒤로 보내는 작업을 진행하면서, 자신이 출력하고자 하는 프린트가 몇 순위로 출력되는지 체크하고 출력한다.

1. 우선순위 큐는 프린트의 우선순위의 순위를 저장하기 위한 큐

2. 일반 큐는 우선순위와 프린트의 인덱스를 저장한다.

3. 그리고 최대 순위는 루프를 한번 회전할때 마다 출력 (루프 한번 당 우선순위큐 pop(), 큐 pop()을 진행)

 

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int testcase;
int n,m;
queue<pair<int,int> >q;
priority_queue<int>pq;
void print(){
    
    int cnt=0;
    while(1){    
        while(1){
            if(q.front().first<pq.top()){
                q.push(make_pair(q.front().first,q.front().second));
                q.pop();
            }
            else break;
        }
        if(q.front().second==m){
            cnt++; break;
        }
        else{
            cnt++;q.pop();pq.pop();
        }

    }
    cout<<cnt<<"\n";
}
int main(){
    cin>>testcase;
    while(testcase--){
        cin>>n>>m;
        for(int i=0;i<n;i++) {
            int temp;cin>>temp;
            q.push(make_pair(temp,i));
            pq.push(temp);
        }
        print();
        while(!pq.empty() ) pq.pop();
        while(!q.empty() ) q.pop();
    }
}

funny algorithms *0*~