[C++] 백준 1966 프린터 큐

1966번: 프린터 큐

 

문제 요약

FIFO - First In First Out 구조로 우선순위에 따라 문서를 인쇄하는 프린터기가 있다. 조건은 다음과 같다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

문제: Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내라.

---

풀이

핵심은 큐를 어떻게 구현하느냐이다.

얼핏 보면 우선순위 큐로 풀 수 있을 것 같지만 STL의 priority queue는 힙 구조로 되어 있다.

문서의 중요도가 중복되지 않는다면 max heap을 사용해서 풀어도 무방하겠지만, 중복되는 경우 힙 구조는 독자적인 정렬법을 사용하므로 문제에 제시된 조건 2와 어긋난다.

 

본 문제는 queue 자료구조만 사용해도 풀 수 있지만, priority queue와 일반적인 queue를 함께 사용하는 코드를 발견하여 그 방식으로 풀어보았다. (=> STL을 이용한 우선순위 큐)

• 'input.txt'에는 문제의 입력값이 주어진다.
• queue에는 각 문서의 중요도와 입력 순서를, priority queue에는 문서의 중요도만 삽입한다.
• queue.front()의 중요도가 priority queue.top()과 일치하는지 확인한다. 일치하지 않으면 pop후 다시 push한다.(queue의 가장 뒤에 재배치)
• 중요도가 일치하면 우선 우리가 원하는 문서인지 확인한다. 원하는 문서라면 출력 후 break, 원하지 않는 문서라면 pop한다.

#include <iostream>
#include <queue>
#include <string>
#include <fstream>
#include <utility>
using namespace std;

int main() {
	int testCases;
	ifstream in("input.txt");
	in >> testCases;

	for (int i = 0; i < testCases; i++) {
		queue<pair<int, int>> queue;
		priority_queue<int> pqueue;
		int numOfDoc, reqOrder;
		in >> numOfDoc >> reqOrder;

		for (int j = 0; j < numOfDoc; j++) {
			int priority;
			in >> priority;
			queue.push({ priority, j });
			pqueue.push(priority);
		}

		int count = 0;
		while(true) {

			// top priority인 경우
			if (queue.front().first == pqueue.top()) {
				count++;
                
				// 원하는 문서라면 출력
				if (reqOrder == queue.front().second) {
					cout << count << endl;
					break;
				}
                	// 원하는 문서가 아니면 pop
				else {
					queue.pop();
					pqueue.pop();
				}
			}
            // top priority가 아니라면 queue의 끝으로 보낸다
			else {
				pair<int, int> temp = queue.front();
				queue.pop();
				queue.push(temp);
			}
		}
	}
	return 0;
}

 

queue만 사용해서 풀 경우 매번 큐를 탐색하여 가장 높은 중요도를 찾아낸 뒤 비교하면 된다.

어느 쪽이 더 나은 풀이일지 모르겠지만 이 방식도 깔끔한 것 같다.

 

 

참고

https://kyunstudio.tistory.com/50