백준 1966번: 프린터 큐

 

 

 

 

 

 

 

queue pair를 활용하는 문제인데 vector를 사용하는 방법과 priority_queue를 사용하는 방법으로 풀어보았다.

 

 

몇번째 출력인지 세는 count 변수가 있어야한다. 

일반 배열이라면 중요도 순으로 정렬 되었을 때 인덱스를 보고 몇번째 출력인지 알수 있겟지만 queue를 사용하기 때문에 그런 접근이 불가능 하므로 top이거나 front일 때 비교하고 pop할때 count++시키면서 세어야한다.

 

 

 

 

queue<pair<int,int>>와 vector

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


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상


	int t, n, m;	//t : testcase // n:문서의수//m:궁금한 문서가 Queue의 어느 위치에 있는지
	int cnt;		//출력 순서
	queue<pair<int, bool>> q; // <우선순위, m번째 수인지 여부(맞다면 true)>

	cin >> t;


	for (int i = 0; i < t; i++) {
		cin >> n >> m;
		vector<int> doc(n);	// 우선순위 비교를 위해 숫자들을 따로 저장해두는 벡터
		for (int i = 0; i < n; i++) {
			cin >> doc[i];
			if (i != m)
				q.push({ doc[i], false });
			else
				q.push({ doc[i], true });
		}

		sort(doc.begin(), doc.end());
		cnt = 0; 
		while (1) {
			if (q.front().first == doc[doc.size() - 1]) {
				cnt++;
				if (q.front().second)
					break;
				else {
					q.pop();
				}
				doc.pop_back();
			}
			else {
				q.push(q.front());
				q.pop();
			}
				
		}

		cout << cnt << "\n";
		while (!q.empty()) q.pop();
	}


	return 0;
}

 

queue pair를 만들 때 m값과 비교하여 second에 bool값으로 넣어둔다.

우선순위를 vector로 입력받고, sort로 중요도를 오름차순으로 정렬한다.

vector내에서 가장 중요도가 높은 것이 가장 마지막에 위치하게 되므로 출력 된 중요도는 vector에서 삭제된다.

 

 

 

 

queue<pair<int,int>>와 priority_queue

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


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int cnt = 0;
		int n, m; 
		cin >> n >> m;
		queue<pair<int, int>> q;
		priority_queue<int> pq;
		
		for (int j = 0; j < n; j++) {
			int k;
			cin >> k;
			q.push({ j,k });
			pq.push(k);
		}
		while (!q.empty()) {
			int index = q.front().first;
			int value = q.front().second;
			q.pop();
			if (value == pq.top()) {
				pq.pop();
				cnt++;
				if (index == m) {
					cout << cnt << "\n";
					break;
				}
			}
			else
				q.push({ index,value });
		}
		
	}



	return 0;
}

 

vector를 사용한 방법에선 sort를 했지만 여기선 필요없는 과정이다.

자동으로 중요도가 가장 높은 것이 priority queue의 top이 된다.