백준 1966번 | 프린터 큐 (C++ 풀이)

  문제  

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

1966번: 프린터 큐

---

  풀이  

• 사용 알고리즘 : 구현
• 사용 자료구조: 큐, 우선순위 큐

큐를 활용하는 문제입니다.

 

이 문제에는 중요한 조건이 있습니다. 인쇄할 차례가 온 어떤 문서를 K라고 할 때, K의 중요도보다 더 높은 중요도를 가진 다른 문서가 있다면, K를 인쇄하지 않고 맨 뒷 순서로 보낸다는 것이죠. 따라서, 이 문제를 풀기 위해선 현재 남은 문서들 중 가장 높은 중요도의 값을 관리해주어야 합니다.

 

이제 저 색칠된 부분을 적절히 구현하여 관리해주면 되는데, 두 가지 방법으로 구현해보겠습니다.

① 완전 탐색

첫 번째 방법은 완전 탐색입니다. 현재 큐에 들어가 있는 문서들의 중요도를 하나씩 비교해보면서 가장 큰 중요도 값을 업데이트 해주는 겁니다. 단순한 방법이지만, 입력으로 들어오는 크기 값이 작기 때문에 이 또한 강력하고 좋은 방법입니다.

먼저 큐에 들어있는 값들을 한바퀴 쭉 돌 것인데, 큐에는 반복자(iterator)가 따로 없기 때문에 방법을 고민해 볼 필요가 있습니다. 제일 간단한 방법은, 큐의 현재 크기 값을 구하고, 그 크기 값만큼 반복문을 돌리면서 pop, push를 반복해주면 됩니다. 이 내용은 밑에 적어놓은 코드를 보면서 이해를 하는 것이 빠를 겁니다.

 

② 우선순위 큐

두 번째 방법은 우선순위 큐입니다. 문제의 입력이 작아서 굳이 사용하지 않아도 되지만, 이런 방법도 있다 정도만 알고 계시면 됩니다.

우선순위 큐를 사용하는 이유는, 여러가지 중요도들 중 가장 큰 중요도 값을 빠르고 쉽게 구할 수 있기 때문입니다. 이를 위해서는 큰 값의 우선순위가 항상 커야 하므로 최대 힙의 형태로 만들어주면 됩니다. 최대 힙 형태의 우선순위 큐를 만들었다면, top() 메서드를 통해 가장 큰 값을 반환받고, pop() 메서드를 통해 가장 큰 값을 삭제시켜주면 됩니다.

 

이제 가장 높은 중요도의 값을 알 수 있다면, 문제가 요구하는 순서대로 구현만 해주면 됩니다.

참고로 큐에 문서의 중요도를 넣은 뒤 push와 pop을 반복하다보면, 그 문서들의 입력 순서가 망가질 수 있으니, 큐에 문서의 중요도를 넣어줄 때 순서쌍 (문서의 중요도, 입력으로 들어온 순서) 처럼 상태를 추가하여 넣어주면 됩니다.

 

---

  코드  

// 우선순위 큐 사용
#include <bits/stdc++.h> 
using namespace std;
const int INF = 2e9;
const int inf = 1e9;

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		queue<pair<int, int>> que;
		priority_queue<int> pq; // 최대 힙 
		for (int i = 0; i < n; i++) {
			int p;
			cin >> p;
			que.push({p, i}); // 문서의 중요도, 해당 문서가 몇번째인지 
			pq.push(p);
		}
		int ans = 1;
		while(1) {
			int p = que.front().first;
			int nth = que.front().second;
			if (p != pq.top()) {
				que.pop();
				que.push({p, nth});
			}
			else {
				if (nth == m) break;
				else {
					que.pop();
					pq.pop();
					ans++;
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

 

// 완전탐색 사용
#include <bits/stdc++.h> 
using namespace std;
const int INF = 2e9;
const int inf = 1e9;

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		queue<pair<int, int>> que;
		for (int i = 0; i < n; i++) {
			int p;
			cin >> p;
			que.push({p, i}); // 문서의 중요도, 해당 문서가 몇번째인지 
		}
		int ans = 1;
		while(1) {
			int maxx = -INF;
			for (int i = 0; i < que.size(); i++) {
				int p = que.front().first;
				int nth = que.front().second;
				maxx = max(maxx, p);
				que.pop();
				que.push({p, nth});
			}
			int p = que.front().first;
			int nth = que.front().second;
			if (p != maxx) {
				que.pop();
				que.push({p, nth});
			}
			else {
				if (nth == m) break;
				else {
					que.pop();
					ans++;
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}