BOJ 1966 · 프린터 큐

알고리즘 분류 : 큐  

큐 자료구조를 이용하는 알고리즘 문제다. 큐(Queue)는 선입선출(FIFO; First In First Out)의 선형 자료구조이다. 먼저 들어간 데이터가 먼저 나온다는 뜻이다. 이 문제는 우선순위가 있는 큐를 이용해야 한다. N개의 문서에서 우선순위가 높은 문서부터 먼저 출력되고, 이때 M번 문서는 몇 번째에 인쇄되는지 출력해야 한다.

• 입력받은 데이터를 큐에 집어넣는다.
• 데이터와 함께 데이터의 인덱스를 별도의 큐로 구성하여 문서 번호를 저장한다.
• 큐에서 나온 데이터가 최댓값이 아니면, 다시 큐에 집어넣고, 이를 반복한다.
• 큐에서 나온 데이터가 M번 문서와 일치하면 꺼낸 횟수를 출력하고 종료한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct printer {
    int d, p;
};

void solve() {
    int n, m;
    queue<printer> q;
    priority_queue<int> pq;
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        int k;
        scanf("%d", &k);
        q.push({i, k});
        pq.push(k);
    }
    int cnt = 0;
    while (true) {
        int doc = q.front().d, prior = q.front().p;
        q.pop();
        int max = pq.top();
        if (prior == max) {
            pq.pop();
            cnt++;
            if (doc == m) break;
        } else {
            q.push({doc, prior});
        }
    }
    printf("%d\n", cnt);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    q = deque()

    def solve():
        cnt = 0
        while q:
            mx = max(q)[0]
            prior, doc = q.popleft()
            if prior == mx:
                cnt += 1
                if doc == m:
                    print(cnt)
                    return
            else:
                q.append((prior, doc))

    for i in range(n):
        q.append((a[i], i))
    solve()

---

참고

• 백준 온라인 저지 : BOJ 1966
• 위키피디아 : 큐