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

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

1966번: 프린터 큐

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int count = 0;
    int test_case;
    cin >> test_case;
    int n, m, ipt;//문서의 개수, 궁금한 문서 위치, 중요도
    for (int i = 0; i < test_case; ++i) {
        count = 0;
        cin >> n >> m;
        queue<pair<int, int>> q;
        priority_queue<int> pq; // 우선순위 큐
        for (int j = 0; j < n; ++j) {
            cin >> ipt;
            q.push({ j, ipt });
            pq.push(ipt);
        }
        while (!q.empty()) {
            int index = q.front().first;
            int value = q.front().second;
            q.pop();//pop it so you can put it in the back if it's wrong
            if (pq.top() == value) {// if the value, which is the next in queue's priority matches the next priority
                pq.pop();
                ++count;
                if (index == m) {
                    cout << count << endl;
                    break;
                }
            }
            else q.push({ index,value });//if it's now suppose to be printed yet, push it back into the very end
        }
    }
    cin >> n;
}

 

두개의 큐를 써서 문제를 해결 할 수 있었다

하나는 순서대로 프린트기에 요청을 저장하는 일반 큐 q

다음은 우선 순위대로 높게 저장하는 priority queue pq

그러나 q는 특별하게 우선순위와 함께 인덱스를 pair로 저장해준다

 

그래서 매번 q의 첫 원소가 pq의 원소와 동일한지 확인 후 아니면 뒤로 보낸다

동일하면 프린트 한다

 

시간 복잡도: O(N^2)*test_cases

공간 복잡도: O(N)