[1966번] 프린터 큐

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Priority Queue

2. Deque

우선순위 큐, 덱 이 두개를 조합하여 문제를 해결 할 수 있다.

우선순위 큐에 의해 가장 높은 수부터 확인하게 되고, 덱에 의해 가장 앞에서 pop하려던 것이 

pq에 아직 더 우선순위가 높은 값이 있어서 pop을 못하고 다시 뒤로 넣거나 

아니면 pop을 할 수 있는 상황을 만들어 줄 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
 
    while (tCase--)
    {
        int n, pos;
        
        scanf("%d %d", &n, &pos);
 
        deque<pii> dq; 
        priority_queue<int> pq;
 
        for (int i = 0; i < n; i++)
        {
            int val;
            scanf("%d", &val);
            dq.push_back({ val, i });
            pq.push(val);
        }
 
        int cnt = 1;
        while(!dq.empty())
        {
            if (pq.top() > dq.front().first)
            {
                dq.push_back(dq.front());
                dq.pop_front();
            }
 
            else
            {
                if (dq.front().second == pos)
                {
                    printf("%d\n", cnt);
                    break;
                }
                dq.pop_front();
                pq.pop();
                cnt++;
            }
            
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>