4. 프린터 큐(Queue)

    4번 문제   

 

www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

---

    내가 풀이한 답   

 

  문제에서 문서의 인덱스를 기준으로 문서를 찾아야 하기 때문에 <int, int> 쌍의 queue 자료구조와 문서의 중요도를 확인하기 위해 priority_queue 자료구조를 사용하였다. priority_queue의 첫 번째 요소와 queue의 중요도가 같지 않으면 queue의 첫 번째 요소를 뒤로 보내고 만약 priority_queue의 첫 번째 요소와 queue의 중요도가 같고 문서의 인덱스와 주어진 문제의 인덱스(m)와 같으면 종료하고 그렇지 않으면 priority_queue의 첫 번째 요소와 queue의 첫 번째 요소를 제거한다. 

 

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int t, i, n, m, j, a, idx, imp, cnt;
	cin >> t;
	for(i=0; i<t; i++){
		cnt=0;
		queue<pair<int, int> > q;
		priority_queue<int> pq;
		
		cin >> n >> m;
		for(j=0; j<n; j++){
			cin >> a;
			q.push({j, a});
			pq.push(a);
		}
		
		while(true){
			idx = q.front().first;
			imp = q.front().second;
			
			if(imp == pq.top()){
				cnt++;
				if(idx==m) break;
				q.pop();
				pq.pop();
			}
			else {
				q.push({idx, imp});
				q.pop();
			}
		}
		cout << cnt << endl;
	}

	return 0;
}