백준 1966 프린터 큐

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

1966번 프린터 큐 문제는 큐와 우선 순위 큐를 이용해서 풀었습니다.

 

프린터에서 문서의 위치와 중요도를 저장하기 위해 큐에는 페어클래스를 각각 저장하였고

 

우선 순위큐는 max heap으로 만들어서 큐의 중요도와 비교를 하였습니다.

 

max heap의 top부분과 큐의 value값이 같아질 때까지 반복문을 돌려서 큐의 front를 back으로 옮기고 

 

두 값이 같아지는 경우 처음에 입력받은 위치값과 큐의 first 값을 비교하여 같다면 위치를 출력하였습니다.

 

두 값이 같아도 위치값이 다르다면 각각 큐에서 pop을 한뒤 다시 반복문을 돌도록 하였습니다.

 

같은 중요도인 문서가 없다면 우선순위 큐만 써서 뽑아야 하는 문서의 중요도와 우선순위 큐에서의 위치만 찾으면 되지만

 

같은 중요도인 문서때문에 큐를 하나 만들어서 비교하며 풀었습니다.

 

 

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
	int T; //테스트 케이스 
	cin>>T;
	
	while(T) {
		priority_queue<int> pq;
		queue<pair<int, int>> q;
		int N,M; //N은 문서의 수 M은 찾을 문서의 위치 
		int max = 0;
		int n = 0;
		
		cin>>N>>M;
		
		for(int i = 0; i < N; i++) { //중요도를 입력받아 두 큐에 저장 
			int x;
			cin>>x;
			pq.push(x);
			q.push(pair<int, int>(i, x));
		}
		
		while(!pq.empty()) { //우선순위 큐와 큐의 값을 비교 
			if(pq.top() != q.front().second) { 
				pair<int, int> p = q.front();
				q.pop();
				q.push(p);
			}
			else {
				if(M == q.front().first) { //두 값이 같은경우엔 찾을 위치M과 큐의 first값 비교 
					cout<<n+1<<endl; //일치하면 출력순서n+1 출력 
					break;
				}
				else {
				pq.pop();
				q.pop();
				n++;
			}			
		}
	}
		T--;
}
	return 0;
}