백준_1966 : 프린터 큐 - C++

문제

---

문제 해석

- 입력이 들어온 순서대로 출력 함

- 만약 현재 출력 할 프린트 물 보다 우선순위가 높은 프린트 물이 있다면 현재 프린트 물을 가장 뒤로 보냄

- 이때 내가 원하는 출력물이 몇번째 출력 되는지 구하면 된다.

---

알고리즘

- 입력값을 queue 에 저장 한다.

- 이와 동시에 우선순위를 따로 다른 우선순위 queue 에 저장 한다.

- 이로써 가장 높은 우선순위가 무엇인지 쉽게 알 수 있다.

- 이 후엔 문제에 나온 그대로 현재 출력 할 우선순위가 우선순위 queue 에서의 가장 높은 우선순위보다 낮으면 뒤로 보내는 작업을 진행한다.

- 그러다 내가 원하는 프린트 물이 출력 되는 번째수를 구해 주면 된다.

---

코드

#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();
            if (pq.top() == value) {
                pq.pop();
                ++count;
                if (index == m) {
                    cout << count << endl;
                    break;
                }
            }
            else q.push({ index,value });
        }
    }
}