[Baekjoon, C++] 1966번 : 프린터 큐

백준 단계별 풀기에서 큐,덱 네 번째 문제이다.
링크는 아래와 같다.

www.acmicpc.net/problem/1966

18258번: 큐 2

---

백준 1966번 문제, 입력, 출력

---

백준 1966번 입출력 예제 1

---

1. priority queue를 사용한다. 일반 queue와 다른 점은 숫자를 push 할 때 자동으로 정렬을 해준다는 점이다. 1 2 3 4 순서대로 넣는다면, 4 3 2 1로 위치하게 된다. priority_queue.top()을 해보면 4가 먼저 나오는 것을 확인할 수 있다.

 

2. queue에 값을 넣을 때 pair를 사용한다. 일반적으로 pair를 사용하려면 utility 라이브러리를 전처리에서 포함시켜줘야하는데, queue 라이브러리에서는 utility 없이 사용할 수 있다. pair를 사용하는 이유는, queue에 push 할 때, 수열의 index값 뿐만 아니라, 해당 index의 우선순위값도 저장하기 위함이다. 

 

3. 따라서, 2개의 queue를 사용한다. queue<pair> 와 priority queue. 큐에서 값을 꺼내서 priority queue의 top과 비교한다. queue에서 꺼낸 값의 우선순위와 우선순위큐의 top값이 같다면 현재 가장 우선순위가 높은 값이고, 먼저 나오게 되는 값이다. 우리가 알고자하는 문서는 아니지만, 문제의 조건에서 차례대로 나오는 숫자라는 것은 분명하다. 우리는 이 값을 카운팅을 해줘야한다. answer++로 나올때마다 1씩 올려준다. 그리고 조건을 하나 더 봐야한다. queue에서 꺼낸 값의 우선순위와 우선순위큐의 top값이 같다면, 해당 값의 Index값이 우리가 찾고자하는 문서의 index 값인지를 비교해야한다. 해당 조건이 만족된다면, 우리가 찾고자 문서이고 몇번째로 나오는지를 출력해야하니 카운팅하고 있던 answer값을 출력해준다.  

---

 

#include<iostream>
#include<queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int numOfTest;

	cin >> numOfTest;

	for (int i = 1; i <= numOfTest; i++) {
		int numOfSeq;
		int idxOfDocument;
		int answer = 0;
		queue<pair<int, int>> que;
		priority_queue<int> pq;
		
		cin >> numOfSeq;
		cin >> idxOfDocument;
		for (int j = 0; j < numOfSeq; j++) {
			int pri;
			cin >> pri;
			que.push({j,pri});
			pq.push(pri);
		}

		while (!que.empty()) {
			int nowIdx = que.front().first;
			int nowPri = que.front().second;
			que.pop();

			if (pq.top() == nowPri) {
				answer++;
				pq.pop();
				if (idxOfDocument == nowIdx) {
					cout << answer << "\n";
					break;
				}
			}
			else {
				que.push({ nowIdx, nowPri });
			}
		}
	}
	
	return 0;
}