[백준/C++] 1966번: 프린터 큐 (우선순위 큐)

 

일단 우선순위 큐를 쓸 줄 몰라서 안쓰고 풀어봤다. queue 뿐만 아니라 vector를 활용해서 다시 큐에 들어가지 않는 프린트물이 생길 때 max값을 갱신하였고, 내 프린트물엔 flag를 1로 주어 같이 queue에 넣어주는 형태로 queue의 자료형이 int쌍이 되도록 설정하였다.

 

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

int main() {


	int test_case;
	cin >> test_case;
	for (int i = 0; i < test_case; i++) {

		//input
		int N, M;
		cin >> N >> M;

		vector<int> for_max;
		queue<pair<int, int>> q;
		for (int j = 0; j < N; j++) {
			int a; cin >> a;
			for_max.push_back(a);
			if (j == M) { q.push({ a,1 }); }
			else q.push({ a,0 });
		}

		//process
		int cnt = 1;
		sort(for_max.begin(), for_max.end());
		while (1) {
			if (q.empty()) {
				cout << cnt << "\n";
				break;
			}
			int temp1 = q.front().first; // 현재
			int flag1 = q.front().second;
			q.pop();

			int max = *max_element(for_max.begin(), for_max.end());
			if (temp1 < max) {
				q.push({ temp1,flag1 }); // 프린트 안하고 다시 큐에 넣는다.
			}
			else {
				if (flag1 == 1) {
					cout << cnt << "\n";
					break;
				}
				else {
					cnt++; //프린트한다.
					for_max.pop_back();
				}

			}

		}

	}
	return 0;
}

 

이후에 우선순위 queue를 이용한 풀이도 배워보았다. 알고보니 우선순위큐는 우선순위순으로 정렬을 해주는 애다. 그래서 top에 제일 우선순위가 높은 애가 존재한다. 내가 만든 vector랑 같은 역할인 것같다. 

 

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

int main() {

	int test_case;
	cin >> test_case;
	for (int i = 0; i < test_case; i++) {

		//input
		int N, M;
		cin >> N >> M;

		queue<pair<int, int>> q;
		priority_queue<int> qq;
		for (int j = 0; j < N; j++) {
			int a; cin >> a;
			q.push({ j,a });
			qq.push(a);
		}

		int count = 0;
		while (!q.empty()) {
			int index = q.front().first;
			int value = q.front().second;
			q.pop();
			if (qq.top() == value) {
				qq.pop();
				++count;
				if (index == M) {
					cout << count << endl;
					break;
				}
			}
			else {
				q.push({ index, value });
				}

		}

	return 0;
}