[1966] 프린터 큐

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

1966번: 프린터 큐

<문제>

제목부터 프린터 '큐'이지만, 사실 큐를 안 쓰고 vector로 정렬해도 풀릴 거 같고..

정렬로 풀리니 우선순위 큐도 가능하겠다.

 

큐에 넣는 데이터를 pair<int, bool>로 넣어서

int는 입력되는 우선순위를 넣고, bool에는 현재 데이터가 탐색 대상인지를 포함시켜주었다.

우선순위의 상태를 나타내는 int[10]을 따로 저장하여, 현재 큐에 존재하는 우선순위들의 분포를 파악할 수 있게 한 뒤,

큐에서 하나 꺼낸 뒤 현재 q.front().first가 우선순위 중 가장 높은 지를 먼저 검사한다.

우선순위가 가장 높다면 그대로 하나 빼주면 되고, 그렇지 않다면 다시 맨뒤에 넣고를 반복하면 된다.

q.front().second가 true인 경우에는 n-q.size()를 출력하고 다음 테스트 케이스로 넘어가면 된다.

 

위 과정을 수행하는 도중, '현재 우선순위의 최대값'을 업데이트해줄 필요가 있는데..

31-37번 라인이 해당 부분을 구현한 부분이 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int t, n, m, mx, p[10];
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        queue<pair<int, bool>> q;
        memset(p, 0, sizeof(p));
        cin >> n >> m;
        int i;
        mx = 0;
        for (i = 0; i < n; i++) {
            int x;
            cin >> x;
            p[x]++;
            mx = max(x, mx);
            bool t = (i == m);
            q.push({x, t});
        }
        int ans;
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            if (cur.first != mx) {
                q.push(cur);
                continue;
            }
            p[cur.first]--;
            if (p[cur.first] == 0) {
                while (1) {
                    mx--;
                    if (p[mx]) break;
                }
            }
            if (cur.second == true) {
                ans = n - q.size();
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}