[백준 1966] 프린터 큐 (C++)

 

Problem

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

1966번: 프린터 큐

 

Comment

상근이가 개발한 프린터에서 돌고 있는 특정 문서의 프린터물 출력 순서를 구하는 문제입니다.

 

상근이가 개발한 프린터가 동작하는 알고리즘은 다음과 같습니다.

 

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

 

우선순위 큐(pq)에는 큐의 우선순위만 담겨있습니다. 그래서 큐(q)에서 하나씩 순차적으로 찾으면서, 만약 큐(q)의 맨 앞에 우선순위가 제일 높은게 나온다면(pq.top() == q.front().second) 빼내서 카운트를 하나 올립니다. 카운트를 선언한 이유는 순서를 찾고 싶은 문서의 현재 위치(docu_rank)와 비교해서 같으면(index == docu_rank) 문서가 몇 번째에 인쇄된 건지 찾은 것이기 때문입니다. 만약 우선순위가 맞지 않거나 현재 위치와 비교해서 맞지 않다면 다시 큐(q) 뒤로 push합니다.

 

예제 1을 차례대로 따라가보겠습니다.

예제 1에서는 3개의 test_case가 주어집니다. 첫 번째 test_case부터 따라가보겠습니다.

 

[test_case 1]

문서 개수(docu_cnt): 1
순서를 찾고 싶은 문서의 현재 위치(docu_rank): 0
문서 우선순위(docu_importance -> q):
5

문서가 하나밖에 없으므로 첫 번째에 인쇄되는것을 바로 알 수 있습니다.

 

[test_case 2]

문서 개수(docu_cnt): 4
순서를 찾고 싶은 문서의 현재 위치(docu_rank): 2
문서 우선순위(docu_importance -> q):
1 2 3 4

2번째 위치에 있는 문서의 우선순위는 3이므로(위치는 0번째부터 존재합니다.) 두 번째에 인쇄될 것입니다. 그러기 위해서는 우선순위 '4'가 pop되어야 하므로 우선순위가 작은 3개의 문서들은 다시 큐로 push 합니다.

 

<2회차>

문서 우선순위(docu_importance -> q):
1 2 3

이제 세 번째 문서가 우선순위가 제일 높게 되었습니다. 우선순위가 3인 값을 찾다가 만나면 출력하고 프로그램은 종료됩니다(여기는 test_case가 남아있어서 다음 test_case로 넘어갑니다.).

 

[test_case 3]

문서 개수(docu_cnt): 6
순서를 찾고 싶은 문서의 현재 위치(docu_rank): 0
문서 우선순위(docu_importance -> q):
1 1 9 1 1 1

우선순위가 같은 문서들이 많이 들어있습니다. 이럴 때는 index가 같은지 비교하는 것(index == docu_rank)이 중요합니다. 일단 우선순위가 제일 높은 문서를 출력합니다.

 

<2회차>

문서 우선순위(docu_importance -> q):
1 1 1 1 1

다시 큐에 넣으면 우선순위가 같아도 뒤로 밀리게 됩니다. 그래서 앞에 있는 문서가 빠져야 차례가 올 겁니다.

 

<3회차>

문서 우선순위(docu_importance -> q):
1 1 1 1

 

<4회차>

문서 우선순위(docu_importance -> q):
1 1 1

 

<5회차>

문서 우선순위(docu_importance -> q):
1 1

이제 0번째 문서의 우선순위가 제일 높게 되었습니다. 우선순위가 1인 값을 찾다가 원하는 문서를 만나면 출력하고 프로그램은 종료됩니다.

 

 

Code

 

Result