cpp) 백준 1966: 프린터 큐

Problem

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

1966번: 프린터 큐

 
 

Solution

#include<iostream>
#include<queue>

using namespace std;

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

    int t;           // 테스트케이스 수
    int n, m, rank;  // 문서의 개수, 궁금한 문서가 몇 번째 놓여있는가, 중요도
    int cnt;         // 몇 번째로 출력되는가 세기 위해 설정

    cin >> t;
    for(int i=0;i<t;i++){
        // 큐 초기화
        queue<pair<int,int>> q;
        priority_queue<int> pq;
        cin >> n >> m;
        cnt=0;

        for(int j=0;j<n;j++){
            cin >> rank;
            q.push({j,rank});
            pq.push(rank);  // 우선순위 큐는 값이 큰 순서대로 정렬됨
        }

        while(!q.empty()){
            int index = q.front().first;
            int value = q.front().second;
            q.pop();
            if(pq.top()==value){
                pq.pop();
                cnt++;
                if(index==m){
                    cout << cnt << '\n';
                    break;
                }
            } else {
                q.push({index,value});
            }
        }

    }
  
    return 0;
}

 
 

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

 
queue에 인덱스와 중요도를 pair로 묶어서 넣어준다. 우선순위 큐를 사용하여 중요도(rank)가 높은 순서대로 정렬시켜준다. (예시: 1,2,3,4 순서대로 넣어주면 4,3,2,1 내림차순 형태로 정렬)
 
pair의 첫 번째 값은 인덱스(index), 두 번째 값은 중요도(value)를 나타낸다. pq.top()은 현재 데이터 상에서 가장 중요도가 높은 값을 나타낸다. 중요도가 높은 값이 먼저 인쇄되므로 pop()을 사용해 우선순위 큐에서 빼주고 cnt를 증가시킨다. 그런데 이 문서가 우리가 궁금해하던 그 문서라면(index=m), 몇 번째로 인쇄되는지 cnt 값을 출력하고 break 문으로 반복문을 탈출한다. 우리가 궁금해하는 문서가 아니라면, 원래 큐의 뒤에 이어 붙여준다.
 
 

Reference

https://numerok.tistory.com/134

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