1966번 프린트 큐

문제 링크 : www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

---

---

<알고리즘>

  1) (문서의 중요도, 몇번째 문서인지)를 pair로 만들어 queue에 저장

  2) priority queue를 이용하여 중요도 순으로 문서 나열

  3) priority queue 와 queue를 비교하며 중요도가 높은 문서일땐 count를 증가(몇번째에 출력되는지 알기 위해)

                                                     더 높은 중요도의 문서가 존재하면 queue의 front를 맨뒤로 이동

  4) 내가 원하는 문서의 번호는 queue에 저장되어 있으므로 이를 통해 멈출 타이밍 잡기

  5) count 출력

 

 

메모리 : 2016KB     시간 : 4ms

#include <iostream>
#include <queue>
using namespace std;

int main() {
	int T = 0;
	cin >> T;
	while (T--) {
		int N = 0;
		int M = 0;
		cin >> N >> M;

		queue<pair<int,int>> q;
		priority_queue<int>pq;
		int input = 0;
		for (int i = 0; i < N; i++) {
			cin >> input;
			pq.push(input);
			q.push(pair<int,int>(input, i));
		}
		
		int count = 0;
		while (true) {
			if (q.front().first == pq.top()) {
				++count;
				if (q.front().second == M) {
					break;
				}
				q.pop();
				pq.pop();
			}
			 else {
				 pair<int, int> temp = q.front();
				 q.pop();
				 q.push(temp);
			 }
		}
		cout << count << "\n";
	}
	return 0;
}

 

+)참고 : twpower.github.io/93-how-to-use-priority_queue-in-cpp

[C++] C++ STL priority_queue 기본 사용법과 예제