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;
}