[BOJ/C++] 1966 프린터 : Priority Queue

문제

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

풀이

큐, 우선순위 큐, pair 자료구조를 적재적소에 이용하니까 완전 쉽게 풀리는 문제였다.

🌻 특히, 우선순위 큐는 최솟값 or 최댓값 뽑아낼 때 진짜 강력한 도구니까 필요한 때에 적절히 사용하자!

1 1 9 1 1 1

큐
(0, 1)
(1, 1)
(2, 9)
(3, 1)
(4, 1)
(5, 1)
(0, 1)

우선순위 큐
1, 1, 9, 1, 1, 1

코드

#include <iostream>
#include <queue>

using namespace std;

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

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

		cin >> N >> M;
		for (int i = 0; i < N; i++) {
			int tmp;
			cin >> tmp;
			q.push({ i, tmp });
			pq.push(tmp);
		}

		while (!q.empty()) {
			int index = q.front().first;
			int value = q.front().second;
			q.pop();
			if (pq.top() == value) {
				pq.pop();
				ans++;
				if (index == M) {
					cout << ans << '\n';
					break;
				}
			}
			else
				q.push({ index, value });
		}
	}

	return 0;
}