[BOJ/C++] 프린터 큐(1966번)

1. 개요

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

1966번: 프린터 큐

1-1. 설명

우리가 프린터기를 사용할 때 출력 순서는 Queue 자료구조와 동일한 FIFO 형태이다. 상근이는 새로운 프린터기 내부 소프트웨어를 개발했는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄하게 된다.

 - 현재 Queue의 가장 앞에 있는 문서의 중요도 확인

 - 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 존재할 시, 인쇄하지 않고 Queue 가장 뒤에 재배치. 그렇지 않으면 바로 인쇄

현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇번째로 인쇄되는지 알아내는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 각 테스트 케이스 수가 주어짐

 - 테스트 케이스 첫 줄에는 문서의 개수 N과 몇번째로 인쇄되었는지 궁금한 순서가 현재 Queue에서 몇번째 놓여있는지 나타내는 정수 M이 주어짐

 - N은 1 이상 100 이하 자연수, M은 0 이상 N 이하

 - 테스트 케이스 둘째 줄에는 N개의 문서 중요도가 주어짐

 - 중요도는 1 이상 9 이하 정수

---

2. 구현

2-1. 풀이

우선 문제를 꼼꼼히 살펴보고 무엇을 요구하는지 확실하게 이해하고 구현을 하자. 제대로 읽지 못하고 넘겨서 잘못 이해해서 조금 헤맸었다. 중요도와 index를 저장할 queue를 생성하고, 중요도를 저장할 배열을 생성하여 내림차순으로 정렬해주었다. 그리고 while문을 통해 우선순위가 높은 순으로 pop할 수 있게끔 구현하였다. 

2-2. 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 100;
int val[MAX_NUM];

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

    int TC, N, M, num, result, idx = 0, queIdx;
    cin >> TC;

    for (int t = 0; t < TC; t++) {
        cin >> N >> M;
        queue<pair<int, int>> que;
        result = 0, idx = 0;
        for (int i = 0; i < N; i++) {
            cin >> num;
            que.push({ num, i });// 중요도와 index 저장
            val[i] = num; // 높은 중요도 저장
        }
        sort(val, val + N, greater<>());

        while (true) {
            num = que.front().first; 
            queIdx = que.front().second;

            if (num == val[idx]) {
                idx += 1;
                result += 1;
                que.pop();
                if (queIdx == M) break;
            }
            else {
                que.pop();
                que.push({ num, queIdx });
            }
        }
        cout << result << "\n";
    }
    return 0;
}