(백준/C++) 1966번_프린터 큐

1966번: 프린터 큐 (acmicpc.net) 문제는큐의 속성을 이해하는 것과 동시에우선순위에 따라 출력하는 것이 핵심인 문제입니다.

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

즉, 우선순위에 따라 인쇄 여부를 결정하고 몇번째 인쇄되는지 찾는 문제입니다.

주의 사항

특히 예제 입력 1 1 9 1 1 1 같은 경우에는 1이 여러 개 있으므로, 출력할 때 그 순서를 카운트할 수 있는 알고리즘이 필요합니다.

---

풀이 과정

저는 이 문제를 풀 때, 문제에서 말한 우선 출력해야 하는 ‘중요도’를 확인하기 위해 우선순위 큐를 생각했습니다.

이 문제는 1 이상 9 이하의 정수로 제한되어 있기 때문에 배열로 풀 수도 있겠지만, 우선순위 큐를 이용해서 O(1)의 시간으로 더 큰 숫자의 여부를 빠르게 파악하고, O(log𝑁)의 시간으로 재정렬 시켜봤습니다.

그리고 여러 개의 1 같은 숫자가 여러 개 있는 경우를 대비하여, 선택된 숫자인지를 확인하기 위해 큐에 int와 함께 bool로 반복문의 종료 지점을 확인하게 했습니다.

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N, elSize, elIndex;
    cin >> N;
    while (N--)
    {
        int count = 0;
        queue<pair<int, bool>> nums;
        priority_queue<int> counter;
        cin >> elSize >> elIndex;
        for(int i = 0; i < elSize; i++)
        {
            int tmp;
            cin >> tmp;
            counter.push(tmp);
            nums.push(pair<int, bool>(tmp, i == elIndex));
        }
        //우선순위에 따라 재정렬
        while (!nums.empty())
        {
            while(nums.front().first != counter.top())
            {
                nums.push(nums.front());
                nums.pop();
            }
            count++;
            
            //원하는 요소에 접근했다면
            if(nums.front().second)
                break;
 
            nums.pop();
            counter.pop();
        }
        cout << count << '\n';
    }
}