[C/C++] 백준 #1966 프린터 큐(구현)

네트워크 프린터에서는 전해진 문서들이 큐에 쌓이고, 차례대로 찍히는 것이 일반적입니다.

 

printer queue

 

이 문제에서의 프린터 큐는 중요도가 있어서, 중요도가 높은 것이 후위에 있으면, 해당 문서를 찍지 않고, 큐의 마지막으로 옮겨지게 됩니다.

 

이번 백준 문제는 이러한 시스템에서 m번째 문서가 몇번째 찍히는지 계산하는 것입니다.

 

문제 뜻대로 그대로 구현을 한다면, 큐에서 문서를 하나 빼낼때마다, 매번 뒤의 문서들을 검색해야 합니다.  이 경우 우선순위가 낮은 것부터 높은것 순서대로 되어 있는 최악의 경우라면, 문서를 검사하는 비용이 \(O(N^2)\)이 됩니다.  사실 N이 100 이하이므로 이렇게 구현을 해도 됩니다.  검사비용말고, 큐에 추가하는 것을 따진다면, 최악의 경우 역시 \(O(N^2)\)이므로, 검사비용이 낮아지는 것으로는 크게 개선이 되지 않습니다.

 

저는 검사비용만 낮아지도록 작성하였습니다.  우선순위가 총 9가지밖에 없기 때문에 배열에 우선순위에 따라 우선순위가 낮은것부터 바로 전까지 빈도를 증가시킵니다.  이 작업에 필요한 것이 \(O(N)\)입니다.  그런다음에 큐에 따라서 우선순위 빈도가 0이 아니면, 현재 문서보다 우선순위가 높은 것이 아직 큐에 존재한다는 뜻이므로 큐의 맨 마지막에 넣기를 합니다.  빈도가 0이라면, 해당 문서를 출력하고, 해당 문서보다 우선순위가 낮은 것들의 빈도를 줄입니다.  결국 이렇게 하면 검색비용이 역시  \(O(N)\)이 됩니다.  검색비용만 줄일 수 있게 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1966
//        - by Aubrey Choi
//        - created at 2019-06-15
//------------------------------------------------
#include <stdio.h>
#include <queue>

int main()
{
    int T;
    scanf("%d", &T);
    for(int t = 0; t < T; t++)
    {
        int n, m, s, p = 0;
        std::queue<int> queue;
        int h[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &s);
            queue.push(s + (i==m)*10);
            for(int j = 1; j < s; j++) h[j]++;
        }
        for(; ; )
        {
            s = queue.front();
            queue.pop();
            if(h[s%10] == 0)
            {
                p++;
                for(int j = 1; j < s%10; j++) h[j]--;
                if(s > 10) break;
            }
            else queue.push(s);
        }
        printf("%d\n", p);
    }
    return 0;
}