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

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

풀이

정렬하는 문제라서 vector를 사용할까 고민했지만, vector를 쓸 경우, 중요도가 높은 문서를 0번째로 가져온 후 나머지 문서들의 위치를 조정하는 것에서 시간이 오래 걸릴 것 같아 queue를 사용했다.

먼저, queue에 {중요도, 초기 순서} 쌍을 저장한다. 그리고 1~9 범위의 중요도 각각의 개수를 배열에 저장해둔다.

queue의 front 요소를 꺼내서, 이것이 중요도가 최대인 문서인지 확인한다. (이때 중요도 개수를 저장해둔 배열 활용)

1. 최대 중요도일 때
   해당 중요도의 개수를 1 감소시키고, 최종 출력 순서(turn)를 1 증가시킨다.
   그리고 해당 문서의 초기 순서가 문제에서 구하고자 하는 m과 같다면 turn을 출력한다.

2. 최대 중요도가 아닐 때
   queue의 맨 뒤에 배치한다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;

int getMax(int* cnt) {
    for(int i=9; i>0; i--) {
        if(cnt[i]) return i;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;

        queue<pi> q;
        int cnt[10] = {0};
        for(int i=0; i<n; i++) {
            int x;
            cin >> x;
            q.push({x, i});
            cnt[x]++;
        }

        int turn = 0;
        while(!q.empty()) {
            pi curr = q.front();
            q.pop();
            if(curr.first == getMax(cnt)) {
                cnt[curr.first]--;
                turn++;
                if(curr.second == m) {
                    cout << turn << "\n";
                    break;
                }
            } else {
                q.push(curr);
            }
        }
    }
    
    return 0;
}