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

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

 

해설

m번째로 뽑아야하는 프린터가 현재 큐에 몇번째에 위치하는지 구하면 되는 문제이다.

까다로운 부분은 중요도가 있는데 가장 중요도가 높은 것보다 현재 큐의 앞부분이 낮다면 다시 뒤에 넣어야한다.

이 중요도로를 우선순위 큐를 통해 빠르게 갱신해줄 수 있다.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>
using namespace std;
using ll = long long;
#define endl "\n"

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

	int n, m, tc;
	cin >> tc;
	while (tc--)
	{
		cin >> n >> m;
		int cnt = 0;
		priority_queue<int> pq;
		queue<pair<int, int>> q;
		for (int i = 0; i < n; ++i)
		{
			int a; cin >> a;
			pq.push(a);
			q.push({ i, a });
		}
		while (!q.empty())
		{
			auto now = q.front(); q.pop();
			if (pq.top() == now.second)
			{
				pq.pop();
				++cnt;
				if (now.first == m)
				{
					cout << cnt << endl;
					break;
				}
			}
			else
				q.push(now);
		}
	}

	return 0;
}

 

후기

처음에 중요도를 deque에 담아 정렬하는 방식을 생각했었는데 이보다 우선순위 큐를 사용하는게 좀 더 효율적이라는 생각이 들었고 deque를 내림차순으로 정렬해서 중요도를 갱신하는것 보다 나은 방법이라는 생각이 든다.