[c++/백준] 1966 프린터 큐

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

1966번: 프린터 큐

 

 

프린트의 중요도가 큰 순서대로 출력해야하기 때문에 우선순위큐를 사용해야한다. 

 

우선 queue의 pair를 사용하여 위치값과 중요도를 입력 받는다. 동시에 우선순위큐에 중요도를 입력 받는다. 

이렇게 되면 우선순위큐에 중요도가 내림차순 형식으로 정렬된다. 

 

내림차순으로 정렬된 우선순위큐의 top과 일반 큐의 중요도가 일치할 때와 일치하지 않을 경우를 나눈다. 

 

일치할 때 cnt++를 하고 현재 위치값이 입력받은 m과 같으면 break를 하고 다음 case를 탐색한다. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int cnt = 0;
	int t, n, m, k;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cnt = 0;
		cin >> n >> m;
		queue<pair<int, int>> q;
		priority_queue<int> pQ;	//기본적으로 내림차순 정렬
		for (int j = 0; j < n; j++) {
			cin >> k;
			q.push({ j,k });
			pQ.push(k);	//중요도 높은 순으로 정렬
		}
		while (!q.empty()) {
			//위치값, 우선순위값 가져온 후 pop 수행
			int index = q.front().first;
			int val = q.front().second;
			q.pop();

			//우선순위 큐의 top과 중요도가 일치하면
			if (pQ.top() == val) {
				pQ.pop();
				cnt++;

				//현재 문서 인덱스가 입력받은 m과 같을 때
				if (index == m) {
					cout << cnt << endl;
					break;
				}
			}
			else
			{
				//q의 중요도가 높지 않으면 큐에 다시 push
				q.push({ index,val });
			}
		}
	}
	return 0;
}

우선순위큐를 사용하는 것은 알았지만 큐의 pair를 사용하는지는 몰랐다. 처음에는 struct로 풀려고 했지만 답이 안나와서 큐로 품,,어렵다 진짜ㅠㅠ갈 길이 멀어요