[C++] 백준 1966: 프린터 큐

문제

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

 

 

풀이

1. 문서의 중요도와 문서의 순서를 queue에 넣는다. 동시에 priority_queue에 문서의 중요도만 넣어준다.
2. priority_queue의 top() 값과 queue의 front()값을 비교하여 현재 인쇄하려는 문서보다 중요도가 높은 문서가 있는지를 확인한다.
3. 만약 문서를 인쇄할 수 있는 경우, priority_queue를 pop() 한다.
4. 만약 문서를 인쇄할 수 없는 경우, queue의 front() 값을 다시 queue에 push 해준다.

 

코드

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

struct Num{
    int value, index;
};

int main()
{
    int t, n , m;
    vector<int> v;
    
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> n >> m;
        
        queue<Num> q;
        priority_queue<int> q_num;
        for(int i=0; i<n; i++){
            int num;
            cin >> num;
            q.push({num, i}); // 현재 가치와 index를 push
            q_num.push(num); // 가치를 push. 내림차순 정렬.
        }
        
        int ans=1;
        while(!q.empty()){
            // q의 맨 앞 원소를 뺀다.
            int cur_value = q.front().value;
            int cur_index = q.front().index;
            q.pop();
           
            // 만약 현재 원소보다 가치 큰 값이 있는 경우, 맨 뒤로 push
            if(cur_value <q_num.top()){
                q.push({cur_value, cur_index});
            }
            
            // 현재 값을 뽑을 수 있는 경우
            else{
                // 현재 원소가 우리가 구해야 값이라면
                if(cur_index == m){
                    v.push_back(ans);
                    break;
                }
                q_num.pop();
                ans++; // 카드 뽑은 횟수 증가
            }
        }
    }
    
    for(int i=0; i<v.size(); i++){
        cout << v[i] << "\n";
    }

    return 0;
}