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

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

1966번: 프린터 큐

 

 

 

우선순위 큐를 사용하면 간단하게 풀 수 있다.  

 

 

#include <iostream>
#include <queue>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    
	int test;
	std::cin >> test;
	while (test--)
	{
		int n, m;
		std::cin >> n >> m; //n은 전체 문서의 개수, m은 원하는 문서의 순서

		std::priority_queue<int> prQue; //우선순위 큐
		std::queue<std::pair<int, int>> que;
		std::pair<int, int> pair;
		for (int i = 0; i < n; ++i)
		{
			std::cin >> pair.first; //중요도
			pair.second = i; //삽입 순서
			que.push(pair);
			prQue.push(pair.first); //우선순위 큐에는 중요도를 넣어줌
		}
		int i = 0;
		while (1)
		{
        	//우선순위 큐의 첫번째(가장 높은 중요도)가 큐의 첫번째와 같으면 인쇄
			if (que.front().first == prQue.top())
			{
				++i;
				if (que.front().second == m) break; //우리가 원하는 문서이면 break
				que.pop();
				prQue.pop();
			}
			else //그렇지 않다면 뒤로 넣는다
			{
				que.push(que.front());
				que.pop();
			}
		}
		std::cout << i << "\n";
	}
}

 

 

백준 풀면서 내가 먼저 정답 맞추기 전에 다른 사람 코드 참고한 적 거의 없는데 이 문제는 모르겠어서 좀 참고해서 풀었음.

 

자신보다 더 높은 중요도의 문서가 존재하는지의 여부를 따지기 위해, 우선순위 큐를 따로 만들어서 중요도를 저장한 후 비교한다는 것이 포인트인 듯