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

문제링크

1966번 프린터 큐

 

 

큐에 pair를 통해 키와 밸류값으로 전달할 수 있고

우선순위 큐와 비교연산자 greater, less 통해 오름차순/내림차순 정렬로 값을 담아낼 수 있다.

기본 우선순위 큐는 내림차순으로 정렬된다.

priority_queue<int, vector<int>, greater<int>> ascendingPQ;	// 오름차순
priority_queue<int, vector<int>, less<int>> descendingPQ;	// 내림차순

 

 

제출코드

#include <iostream>
#include <queue>

using namespace std;

int T, N, M, out;

int main()
{
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		out = 0;
		cin >> N >> M;

		queue<pair<int, int>> q;	// 큐에 인덱스와 중요도 값을 저장
		priority_queue<int> pq;		// 우선순위 큐 (자동 내림차순)
		for (int j = 0; j < N; j++)
		{
			int val = 0;
			cin >> val;
			q.push(make_pair(j, val));
			pq.push(val);
		}

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

			if (pq.top() == val)
			{
				pq.pop();
				out++;
				if (idx == M)		// 원하는 인덱스와 큐에 있는 인덱스가 동일하면 출력
				{
					cout << out << endl;
					break;
				}
			}
			else
			{
				q.push(make_pair(idx, val));	// 일치하지 않으면 다시 큐에 집어넣음
			}
		}
	}

	return 0;
}