[백준 1966번] 프린터 큐

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

1966번: 프린터 큐

 

📍 문제

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

 

총 정리를 해보면 나오는 사진

 

1. 그럼 test_case로 총 테스트 케이스 갯수를 받는다

2. 그리고 for문을 활용/while문을 활용하여 testcase를 하나씩 삭제한다

3. for문/while문 속 문서의 갯수가 몇 개인지 입력하고 궁금한 문서가 현재 큐에서 몇 번 째 놓여 있는지 나타내는 정수도 입력시킨다

4. 중요도는 큐 pq를 활용하여 넣는다(pq는 우선순위 큐, q는 그냥 queue)

5. pq는 priority_queue로써 우선순위가 높은 것부터 out 시킨다

6. for문을 활용하여 q와 pq에 입력시킨다.

7. q가 없어질 때까지 while문을 활용하는데 이 while문 안에는 pq의 맨 앞 큐와 q의 두 번째 값(즉, 중요도)가 같으면 배출 시키고 아니면 다시 q 뒤에 추가시킨다.

8. 이를 계속하여 반복시킨다

 

 

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

int main(){
    int count=0;
    int testcase;
    int n, m, impt; // 문서의 개수, 문서 위치, 중요도

    cin>>testcase;
    for(int i=0;i<testcase;i++){
        count=0;
        cin>>n>>m;

        queue<pair<int, int> > q;
        priority_queue<int> pq; //우선순위 큐

        for(int j=0;j<n;j++){
            cin>>impt;
            q.push( {j, impt});
            pq.push(impt);
        }
        while (!q.empty())
        {
            int index=q.front().first;
            int value=q.front().second;
            q.pop();
            if(pq.top()==value){
                pq.pop();
                ++count;
                if(index==m){
                    cout<<count<<endl;
                    break;
                }
            }
            else q.push( {index, value});
        }
    }
    return 0;
}