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

"우선순위"에 따른 출력 순서를 알아내야 하므로 우선순위 큐를 쓴다.

우선순위 큐(Priority Queue)는 들어온 순서가 아닌 우선순위에 따라 먼저 처리되는 구조이다.

우선순위 큐 - https://zoosso.tistory.com/993 참고

#include <iostream>
#include <queue>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T, N, M, pr;
	queue<pair<int, int>> q;
	priority_queue<int> pq;
	
	cin >> T;
	
	while (T--) {
		cin >> N >> M;
		int cnt = 0;

		for (int i = 0; i < N; i++) {
			cin >> pr;

			q.push({ i, pr });
			pq.push(pr);
		}

		while (!q.empty()) {
			int idx = q.front().first;
			pr = q.front().second;

			q.pop();

			int now = pq.top();
			if (now == pr) {
				pq.pop();
				cnt++;
				if (idx == M) {
					cout << cnt << endl;
				}
			}
			else {
				q.push({ idx, pr });
			}
		}
	}
	

	return 0;
}