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

문제

1966번: 프린터 큐

---

문제 요약

중요도가 높은 순서대로 문서를 인쇄하면서, 특정 문서가 몇 번째로 인쇄됐는 지 출력하는 문제이다.

---

코드

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

using namespace std;

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int T; cin >> T;
    int N, M, save, index = 0, order = 1;
    bool bigger = false;

    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        order = 1;
        bigger = false;
        queue <int> seq;
        vector <int> imp(N);

        for (int j = 0; j < N; j++) {
            cin >> imp[j];
            seq.push(j);
        }

        while (!seq.empty()) {

            for (int k = 1; k < imp.size(); k++) {
                if (imp[0] < imp[k]) {
                    bigger = true;
                    break;
                }
                else {
                    bigger = false;
                }
            }

            if (bigger == true) {
                seq.push(seq.front());
                seq.pop();

                imp.push_back(imp[0]);
                imp.erase(imp.begin() + 0);
            }
            else {
                if (seq.front() == M) {
                    cout << order << '\n';

                    seq.pop();
                    imp.erase(imp.begin() + 0);
                    break;
                }
                else {
                    order++;

                    seq.pop();
                    imp.erase(imp.begin() + 0);
                }
            }
        }
    }

    return 0;
}

---

문제 풀이

1. int형 vector에는 순서대로 문서의 중요도를 저장하고 int형 queue에는 문서의 번호를 저장한다.

2. queue의 원소가 모두 없어질 때까지 반복한다.

• 만약 vector 내에 0번째 문서(인쇄 대기 중인 문서)보다 중요도가 높은 문서가 있다면 bigger를 true로 초기화
• bigger가 true라면 0번째 문서를 맨 뒤로 보내고, queue 내에서도 가장 후방(rear)으로 보낸다.

• 만약 vector 내에 0번째 문서보다 중요도가 높은 문서가 없다면 bigger는 false
• bigger가 false라면 0번째 문서를 vector 내에서 삭제하고, queue를 삭제하는 데, 그 전에
• 만약 queue의 front가 특정 문서의 번호 M과 같다면 몇 번째 인쇄인 지를 나타내는 변수 order를 출력한다.
• 다르다면 order를 +1 해주고 queue의 front를 삭제한다.

끝

---

잡담

queue의 정렬에 대해서 찾아보다가 우선순위 큐라는 것을 찾았다.

처음에는 이걸 적용해보려고 했는데, 뭔가 복잡해질 것 같아서 포기했다.

나중에 이 문제를 다시 풀 때는 우선순위 큐를 사용해보는 것도 좋을 거 같다.