Written by JS970
on February 3, 2023

1966 - 프린터 큐

난이도: 실버 3
날짜: 2023년 2월 3일
상태: Correct
추가 검토 여부: Yes

solution

deque와 priority_queue를 사용했다.
deque에는 pair<int, int>가 들어간다.
pair자료구조는 vector, algorithm헤더에 포함되는 자료구조이다.
pair.first는 priority정보를, pair.second는 index정보를 저장한다.
priority_queue는 중복을 허용하는 max heap으로 동작할 수 있으므로 이를 deque의 pair.first(priority)값과 비교하여 현재 출력 순서가 아니라면 deque.pop_front한 후 deque.push_back을 통해 순서를 맨 뒤로 보낸다. 만약 출력 순서라면 deque.pop, priority_queue.pop을 수행하고 출력 순서를 나태나는 변수인 order를 1만큼 증가시킨다. 이후 프린터의 다음 출력 순서를 탐색한다.
이 과정을 deque.second == M일때까지 반복한다.
deque.second == M일때의 order를 출력한다.

code

#include <iostream>
#include <deque>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    int testC, N, M;
    cin >> testC;
    for(int count = 0; count < testC; count++)
    {
        cin >> N;
        cin >> M;
        deque<pair<int, int>> print;
        priority_queue<int> pq;
        int prio;
        for(int i = 0; i < N; i++)
        {
            scanf("%d", &prio);
            print.push_back(make_pair(prio, i));
            pq.push(prio);
        }

        pair<int, int> p;
        int order = 1;
        while(1)
        {
            if(print.front().first != pq.top())
            {
                p = print.front();
                print.pop_front();
                print.push_back(p);
            }
            else
            {
                if(print.front().second == M) break;
                print.pop_front();
                pq.pop();
                order++;
            }
        }
        cout << order << endl;
    }
    return 0;
}

ref

C++ STL priority_queue 우선순위 큐 사용법

1966번: 프린터 큐

Top