[백준] 1966번 - 프린터 큐 c++

✍ 입출력

입력: T(테스트 케이스)
N(문서의 개수), M(주목할 index)N개 만큼의 P들(중요도)
출력: 주목하는 index가 몇번째로 pop 되어서 나오느냐 출력

Key point: 문서의 갯수가 중요도와 함께 저장되어야 한다.

queue<pair<int,int>> queue;

queue 안에 pair를 넣게 되면 두 가지 값(index, 중요도)을 같이 저장할 수 있다.

pair를 사용하면 일반 queue와 다른 점이 존재한다.

priority_queue<int>pq;

priority queue에 들어가게 되면 내림차순으로 자동적으로 정렬된다. (ex. 7...4...1...)

그럼 작은수 부터 쓰려면 어떻게 해야 할까?

priority_queue<자료형,구현체,비교연산자> 형식으로 구현해야한다.

오름차순으로 정렬하려면 greater를, 내림차순이면 less를 비교연산자로 사용할 수 있다.

priority_queue<int,vector<int>,grater<int>>pq;

---

📖 해결법

1.PQ에 중요도를 저장한다. Queue에 index와 중요도를 저장한다.
2. queue가 empty가 될 때 까지 while문을 돈다. while문 안에서는 PQ에 첫번째 값(우선순위가 가장 높음)이랑 우선순위가 같은지 if문 으로 체크한다. 만약 같다면 index값이 전에 입력받은 M과 같은지 체크한다. 이것도 같다면 count 출력 후 break로 while문 탈출.

우선순위만 같다면 일단 pop 해야하니 count 값 1 증가시켜주고 queue랑 PQ pop 기능 실행시켜준다.

3.처음 if문(PQ 우선순위 값과 같지 않다면) else로 가서 queue 값을 pop 후 다시 push.

4.pop 한것이 미리 저장되어있어야 push 할 수 있으니 location,value 변수를 선언해서 while 문 시작부분에 위치시켜준다.

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


int main() {
	int T;
	cin >>T;
	
	while (T--) {
		priority_queue<int>pq; // pq안에 들어가면 내림차순으로 구현됨 7 3 1 
		queue<pair<int,int>> queue;
		int N, M, P;
		cin >> N >> M;

		for (int i = 0; i < N; i++) {
			cin >> P; //우선순위
			pq.push(P); 
			queue.push({ i, P });
		}
		int count = 0;
		while (!queue.empty()) {
			int location = queue.front().first;
			int value = queue.front().second;

			if (pq.top() == queue.front().second) { //우선순위 체크
				count++;
				queue.pop();
				pq.pop();
				if (M == location) {
					cout << count << endl;
					break;
				}
			}
			else {
				queue.pop();
				queue.push({ location,value });
			}
		
		}
	
	
		
		
	}
}