백준 01966 - 프린터 큐

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

1966번: 프린터 큐

 

고려사항

- 1번째 부터 시작이니 최종 ans + 1 출력.

- q에는 몇번 째 수 인지 나타내는 idx도 페어로 삽입.

- 실제 프린터 대기열인 q의 front와 정해진 다음 출력 우선순위를 나타내는 pq의 top 을 비교.

- 우선순위가 같으면서 idx까지 m 과 같다면 정답출력, 아니면 pq, q에서 pop 후  ans += 1;

- 우선순위가 다르면 맨뒤로 삽입

 

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

int main() {
    int n, m, t, num, target, ans;

    cin>>t;
    for(int i=0;i<t;++i){
        priority_queue<int> pq;
        queue<pair<int, int>> q;
        ans = 0;

        cin>>n>>m;
        for(int j=0;j<n;++j){
            cin>>num;
            if(j == m){
                target  = num;
            }
            pq.push(num);
            q.push({num, j});
        }

        while(true){
            if(q.front().first == target && pq.top() == q.front().first && q.front().second == m){
                cout<<ans+1<<"\n";
                break;
            }else if(q.front().first == pq.top()){
                pq.pop();
                q.pop();
                ++ans;
            }else{
                q.push({q.front().first, q.front().second});
                q.pop();
            }
        }
    }
    return 0;
}