[BOJ] 1966 프린터 큐

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

1966번: 프린터 큐

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

queue

 

---------------------------------------------------풀이----------------------------------------------------

 

우선, importance[]에 각 프린트물의 중요도의 개수를 저장한다.

예를 들어, 1 1 1 3 4 이면, importance[1] = 3, importance[3] = 1, importance[4] = 1 이다.

 

큐에 각 프린트물을 순서대로 저장한다.

원래의 인덱스와 프린트물의 중요도를 pair로 함께 저장한다.

 

문제 조건에 맞게 원하는 인덱스(M)이 출력될 때까지 반복한다.

queue의 front의 중요도보다 큰 프린트물이 뒤에 존재하면, 즉, importance[front 중요도보다 큰 수] > 0 이면 뒤로 push한다.

없다면 pop하는데, importance[front 중요도]를 1 감소시키고, 그 프린트물이 M이면 종료한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main(void){
    FASTIO;
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        int N, M;
        cin >> N >> M;
        // 각 중요도 개수를 저장
        int importance[10] = {0, };
        // 인덱스, 중요도
        queue<pair<int,int> > q;
        pair<int,int> p;
        for(int i = 0; i < N; i++){
            cin >> p.second;
            p.first = i;
            q.push(p);
            importance[p.second]++;
        }
        int turn = 0;
        while(!q.empty()){
            bool print_flag = true;
            for(int i = 9; i > q.front().second; i--){
                if(importance[i] > 0){
                    print_flag = false;
                    break;
                }
            }
            if(print_flag){
                turn++;
                if(q.front().first == M){
                    break;
                }
                importance[q.front().second]--;
                q.pop();
            }
            else{
                q.push(q.front());
                q.pop();
            }
        }
        cout << turn << "\n";
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

priority queue로 우선순위에 따라 출력하는걸 먼저 생각했지만,

그런 방식으로는 동일한 우선순위의 프린트물에 대해강제로 우선순위가 부여되기 때문에

상황에 따라 변화하도록 해야하는 방식인 이 문제와는 맞지 않을 거라고 생각했다.