[백준] 1966번: 프린터 큐

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

1966번: 프린터 큐

문제 이해

FIFO 방식이라고 했으므로 큐를 이용하는 문제이다. 

문서를 앞부터 하나하나 체크하면서, 뒤에 우선순위가 자기보다 높은 애가 있으면 프린트하지 않고 다시 큐의 뒤에 넣어준다.

 

관건은 우선순위가 자기보다 높은 애가 있는지를 판단하는 것이다. 

우선순위가 1부터 9로 범위가 작으므로 각 우선순위 별로 문서가 몇 개가 있는지를 확인하면 편하다. 

이를 위해서 우선순위 별 문서 수를 저장한 배열을 이용하면 된다. 

 

주의할 점은 테스트 케이스가 여러 개이므로 초기화가 필요하다는 것이다.

만약 모든 문서를 출력하기 전에 정답이 나왔으면, 큐에 아직 데이터가 남아있으므로 큐를 비워줘야 하고, 우선순위 별 문서 개수를 저장한 배열도 비워줘야 한다. 

작성 코드(C++)

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

using namespace std;

int T, N, M; // 테스트 케이스 개수, 문서의 개수, 순번을 알아내야 할 문서 번호
queue<pair<int, int> > q; // 프린터 큐

int priority[10]; // 우선순위 별 개수 저장
vector<int> answer; // 답을 저장할 벡터

void getInput() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int p;
        cin >> p;
        q.push(make_pair(i, p));
        priority[p]++;
    }
}

void Solve(void) {
    int cnt = 0; // 프린트
    // 입력 받기
    getInput();

    // priority의 모든 문서 수가 0이 될 때까지
    for (int i = 9; i > 0; i--) {
        while (priority[i] > 0) {
            pair<int, int> cur = q.front();
            q.pop();

            if (cur.second == i) { // 프린트 가능
                cnt++;
                priority[i]--;
                if (cur.first == M) { // 목표 문서이면
                    answer.push_back(cnt);
                    return;
                }
            }
            else { // 프린트 불가능
                q.push(cur); // 큐에 다시 넣어줌
            }
        }
    }
}

int main(void) {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 입력 받기 
    cin >> T;
    for (int t = 0; t < T; t++) {
        if (t > 0) {
            // 초기화 필요
            while (!q.empty()) q.pop();
            for (int i = 1; i <= 9; i++) {
                priority[i] = 0;
            }
        }
        // 테스트 케이스별 동작
        Solve();
    }

    for (int t = 0; t < T; t++) {
        cout << answer[t] << "\n";
    }
    return 0;
}