백준 1966: 프린터 큐 (C++)

문제 링크: www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

큐와 우선순위 큐를 활용해 해결하는 문제다.

입력받을 때 큐에 {문서의 순서, 중요도}를 pair를 활용해 저장했고, 우선순위큐에 중요도를 넣어주었다.

이후 큐에 있는 모든 문서가 처리될 때까지 while문으로 반복한다.

맨 앞에 있는 문서를 꺼낸 다음(q.pop()) 해당 문서의 중요도가 남아있는 모든 문서 중 가장 높은 중요도와 일치하면(현재 문서의 중요도가 가장 높다는 뜻) 몇번째 출력인지 나타내는 count변수에 1 더해주고, 우선순위 큐에서 pop해준다. 만약 그렇지 않으면 다시 큐에 넣는다.

우선순위 큐에서 pop할 때(이번에 출력하려던 문서의 중요도가 남아있는 문서 중요도 중 가장 높았을 때), 이번에 출력한 문서가 몇 번째로 인쇄되었는지 궁금한 문서(m)라면 몇 번째로 인쇄되었는지 출력해주고 이번 테스트케이스를 끝낸다.

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int caseNum = 0;

    scanf("%d", &caseNum);

    for (int i = 0 ; i < caseNum ; i++) {
        int n, m, in, count=0;
        queue <pair<int, int>> q;
        priority_queue<int> pq;

        scanf("%d %d", &n, &m);

        for (int j = 0; j < n ; j++){
            scanf("%d", &in);
            pq.push(in);
            q.push({ in, j });     
        }

        while (!q.empty()) {
            int imp = q.front().first; 
            int index = q.front().second;
            q.pop();

            if (pq.top() == imp) {
                pq.pop();
                count++;
                if (index == m) {
                    printf("%d\n", count);
                    break;
                }
            }
            else {
                q.push({ imp,index });
            }
        }
    }
}

 

꽤 이전에 푼 문제인데 지금이라면 몇 번째 문서인지와 해당 문서 중요도를 저장하는 큐를 만들지 않고 우선순위 큐에 pair로 저장할 것 같다. (우선순위 큐에 따로 지정을 하지 않으면 pair중 first가 기준이되므로)