본문 바로가기

Problem Solving/Algorithm Training

[Baekjoon] 1966 - 프린터 큐 (C++)

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

 

1966번: 프린터 큐

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를

www.acmicpc.net

중요도가 높은 문서를 먼저 뽑고, 중요도가 낮은 문서는 맨 뒤로 밀려나는 상황에 특정 문서가 몇 번째로 인쇄되는지 구하는 문제입니다.

 

일단 중요도를 무시한다면 먼저 들어온 문서를 먼저 인쇄하면 되기에 큐(queue)를 사용하면 될 것 같다는 생각이 들었습니다. 하지만 중요도를 매번 비교하면서 현재 문서보다 더 높은 중요도의 문서가 있으면 맨 뒤로 보내야 하는 과정이 필요합니다.

 

즉, 뽑아야 하는 문서 중에서 매번 가장 높은 중요도가 무엇인지 알아야 할 필요성이 있다는 것이죠. 항상 제일 큰 값을 찾아야 한다? 이러면 떠올라야 하는 자료구조가 하나 있죠. 바로 우선순위 큐(priority queue)입니다. 이를 사용하면 아주 쉽게 가장 높은 중요도를 바로 구할 수 있습니다.

 

큐와 우선순위 큐 모두 C++ STL에서 기본으로 제공하고 있으니 바로 가져다 사용하시면 됩니다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	cin >> t;

	while (t--) {
		int n, m;
		cin >> n >> m;

		// 문서 정보
		queue<pair<int, int>> docList;

		// 가장 높은 중요도를 바로 파악할 수 있도록 우선순위 큐 사용
		priority_queue<int> maxImportance;

		// 인쇄 횟수
		int printCount = 0;

		// 데이터 입력
		for (int i = 0; i < n; i++) {
			int value;
			cin >> value;

			docList.push(make_pair(i, value));
			maxImportance.push(value);
		}

		// 인쇄 시작
		while (!docList.empty()) {
			int index = docList.front().first;
			int importance = docList.front().second;

			// 중요도가 더 높은 문서가 있을 경우 맨 뒤로 보냄
			if (maxImportance.top() > importance) {
				docList.push(docList.front());
				docList.pop();
			}
			// 그렇지 않으면 인쇄
			else {
				docList.pop();
				maxImportance.pop();
				printCount++;

				// 궁금한 문서가 인쇄됐을 경우
				if (index == m) {
					// 결과 출력
					cout << printCount << "\n";
					break;
				}
			}
		}
	}

	return 0;
}