[백준] 알고리즘 1966번 - 프린터 큐 문제

#include<bits/stdc++.h>
using namespace std;
queue<pair<int,int>> qu;
priority_queue<int> pq;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n, m,cnt=0;
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			int c;
			cin >> c;
			qu.push({ i, c });
			pq.push(c);
		}
		while (!qu.empty()) {
			int index = qu.front().first;
			int value = qu.front().second;
			qu.pop();
			if (pq.top() == value) {
				pq.pop();
				cnt++;
				if (index == m) {
					cout << cnt << "\n";
				}
			}
			else qu.push({ index, value });
		}

	}
}

 

---

큐에 <인덱스번호,중요도> 이런 쌍으로 저장할 수 있습니다.  queue<pair<int,int>>

C++ 에서 지원하는 우선순위 큐를 이용한다.

우선순위 큐 함수를 이용해서 우선순위를 순서대로 저장할 수 있다.

• 젤 위에 있는 것 반환 : top()
• 삽입 : push()
• 삭제 : pop()

나머지는 큐와 비슷하다.

큐의 앞부분의 쌍을 변수에 저장시킨 후, 제거한다.

이후에 우선순위 큐의 젤 윗부분(가장 먼저 인쇄를 해야하는 값)과 변수와 비교

만약 다르다면, 다시 큐에 쌍을 삽입하여 준다. ( 이경우에는 우선순위가 먼저 뽑혀야 하는 것보다 밀리기 때문에 뒤로 가는 것이다.)