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

www.acmicpc.net/problem/1966

1966번: 프린터 큐

현재 인쇄 명령의 우선순위가 가장 높으면 인쇄를 하고 아니면 맨 뒤로 보냅니다. 이 중 최초로 입력된 명령들 중 m번째 명령이 몇 번째로 실행되는지 찾으면 되는 문제입니다. 예제 입력 중 두 번째의 경우로 살펴보겠습니다.

번호	0	1	2	3
우선 순위	1	2	3	4

queue에 위 표와 같은 형태로 push가 되어 있다고 가정합니다. 아마도 queue<pair<int,int>>의 형태로 선언했을 겁니당. 여기서 높은 우선순위부터 저장되어있는 자료구조를 하나 만듭니다. 일반 배열이 되어도 상관없고 우선순위 큐나 벡터를 써도 됩니다.

우선 순위(내림차순)

4

3

2

1

위 표와 같은 형태로 저장이 되게 될 겁니다. 이제 가장 큐의 가장 앞선 명령의 우선순위가 현재 가장 높은 우선순위와 같은지 비교하여 맨 뒤로 보내거나 pop을 해주면 됩니다. 아래 표로 보겠습니다.

번호	0	1	2	3
우선 순위	1	2	3	4
우선 순위(내림차순)	4	3	2	1
비교	1 == 4 → FALSE

번호	1	2	3	0
우선 순위	2	3	4	1
우선 순위(내림차순)	4	3	2	1
비교	2 == 4 → FALSE

번호	2	3	0	1
우선 순위	3	4	1	2
우선 순위(내림차순)	4	3	2	1
비교	3 == 4 → FALSE

번호	3	0	1	2
우선 순위	4	1	2	3
우선 순위(내림차순)	4	3	2	1
비교	4 == 4 → TRUE(pop)

번호	0	1	2
우선 순위	1	2	3
우선 순위(내림차순)	3	2	1
비교	1 == 3 → FALSE

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int printed(int num, queue<pair<int, int>>& q, vector<int>& imps)
{
    int order = 1;
    while (true) {
        if (q.front().second == imps.front()) {
            if (q.front().first == num) {
                return order;
            }
            q.pop();
            imps.erase(imps.begin());
            order++;
        }
        else {
            q.push(q.front());
            q.pop();
        }
    }
}

int main(void)
{
    int t; cin >> t;

    for (int i = 0; i < t; i++) {
        int n, num; cin >> n >> num;
        queue<pair<int, int>> q;
        vector<int> imps;
        for (int j = 0; j < n; j++) {
            int imp; cin >> imp;
            q.push(pair(j, imp));
            imps.push_back(imp);
        }
        sort(imps.begin(), imps.end(), greater<>());
        cout << printed(num, q, imps) << "\n";
    }

    return 0;
}