백준 1966 C++ - 프린터 큐

Intro

문제해결 및 소스코드

#include <iostream>
#include <queue>

using namespace std;

/*									<문제해결>
		규칙1. 현재 Queue의 가장 앞에 있는 문서의 중요도를 확인한다.
		규칙2. 나머지중에 현재 문서보다 중요도가 높은 문서가 하나라도 있다면 이 문서를 인쇄하지않고 가장 뒤에 재배치한다.
		규칙3. 그렇지 않다면 인쇄한다.

		이 문제는 큐와 우선순위큐를 사용한다면 쉽게 해결할 수 있다.
		먼저 큐에 문서의 인덱스와 중요도를 한쌍으로 넣는다.
		우선순위 큐에는 중요도만 넣는다.
		-> 우선순위 큐는 자동으로 크기가 큰 순으로 정렬된다.

		그 다음 큐에서 원소를 하나씩 pop하여 그 원소의 중요도가 가장높은지 확인한다(우선순위 큐의 top과 비교)
		1. 중요도가 가장 높다면 우선순위 큐의 top도 pop한다.
			1.1 count를 +1 한다.
		2. 중요도가 가장 높지 않다면 큐에서 pop한 원소를 다시 뒤로 넣어준다.
*/

int main()
{
	int testcase;
	cin >> testcase;

	for (int i = 0;i < testcase;i++)
	{
		int n, m;
		cin >> n >> m;
		queue<pair<int, int>> que1;			// .. 문서번호와 중요도를 저장할 큐
		priority_queue<int> que2;			// .. 중요도를 저장할 큐

		int importance;
		int count = 0;
		for (int j = 0;j < n;j++)
		{
			cin >> importance;
			que1.push({ j, importance });
			que2.push(importance);
		}

		while (!que1.empty())
		{
			int index = que1.front().first;		// .. 큐의 first는 index(인덱스)
			int value = que1.front().second;	// .. 큐의 second는 value(중요도)
			que1.pop();							
			if (que2.top() == value)			// .. 큐에서 꺼낸 원소의 중요도가 가장 높다면
			{
				que2.pop();						// .. 우선순위 큐에서도 꺼내어 count를 증가시킨다.
				count++;
				if (index == m)					// .. 인덱스가 찾고자하는 문서의 인덱스라면 순서를 출력하고 멈춘다.
				{
					cout << count << "\n";
					break;
				}
			}
			else
				que1.push({ index, value });	// .. 큐에서 꺼낸 원소의 중요도가 가장 높지않다면 다시 큐에 집어넣는다.
		}
	}
}