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

문제

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

문제 해석

우선순위가 높은 것을 먼저 프린트 하는 조건에서, 우선순위 큐를 이용해 풀이하는 것이라고 짐작할 수 있다. 이때, 단순히 우선순위가 높은 순서대로 출력하는 것이 아니라 특정 위치가 언제 출력되는지가 중요하므로, (위치, 우선순위)를 큐에 가지고 있어야 한다.

(위치, 우선순위)를 큐에 저장한다면, 우선순위를 우선순위 큐에 담아야 한다. 큐 front의 우선순위가 우선순위 큐의 값과 같다면, 출력한다.

구현 방향

변수 선언

테스트 케이스를 전부 수행하면서 변수들을 재사용하기 때문에, q와 pq를 전역으로 선언하면 안된다.

queue와 priority_queue모두 #include <queue>에 존재하고, queue에는 위치와 중요도를 담아야 하기 때문에 pair를 사용한다.

int ordering = 0; // 출력 순서
int T; // 테스트 케이스
int N, M; // 문서의 개수, 궁금한 문서의 위치
int value; // 문서의 중요도 값

queue<pair<int, int>> q; // (위치, 중요도)
priority_queue<int> pq; // 우선순위 큐

우선순위 비교

q의 중요도가 현재 pq의 top 값과 같다면, 존재하는 문서들 중 우선순위가 가장 높아 프린트할 차례이다.

프린트 순번을 기록하는 ordering 변수를 증가시키고, 만약 궁금했던 문서의 위치와 같다면 순번을 출력한다. 우선 순위가 낮다면, q에 다시 push 한다.

while (!q.empty()) {
    int index = q.front().first;
    int important = q.front().second;

    q.pop();

    if (pq.top() == important) {
        pq.pop();
        ordering++;
        if (index == M) {
            cout << ordering << "\n";
            break;
        }
    }
    else q.push({ index,important });
}

전체 코드

[백준/C++] 1966번 프린터 큐 / 풀이 코드