[Silver3] No.01966 프린터 큐
03 Mar 2022프린터 큐
문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
풀이
해당 문제는 큐(Queue)에 해당하는 문제입니다. Stack에 대한 구현 및 설명은 해당 링크를 참조해 주세요.
문제에 있는 예시의 경우 처음 프린트 명령이 들어왔을때 아래와 같이 볼 수 있다.
기존의 큐의 방식처럼 FIFO(First In First Out)의 방식이었다면 순번을 순차적으로 0, 1, 2, 3 순으로 출력 해주면 되겠지만, 문제에서는 ‘중요도’가 높은 문서 먼저 출력 해야한다는 조건이 주어졌다. 문제에서 주어진 예시중 A의 문서가 출력된 순서를 알아보자.
먼저 큐의 문서 A를 poll해서 가져온다.
기본적은 큐의 형태였다면 A의 문서는 가장 먼저 출력되어 1번째로 출력된 문서가 됐을것이다. 하지만 문제에서 중요도의 순으로 출력하라는 조건이 추가된 만큼 큐안에 있는 노드들의 중요도와 비교를 해준다. 만약 중요도가 가장 큰 문서였다면 그대로 출력(poll)시키면 되겠지만, 중요도가 크지않다면 큐의 뒤에 재배치(add) 해주면 된다.
A문서의 경우 중요도가 2로 큐안에 더큰 중요도를 가진 문서가 있으니 출력하지 않고 뒤로 다시 add해준다.
중요도가 가장 높은 문서가 나온다면 그대로 출력(poll) 해버리면 된다.
해당 과정을 반복하다 보면 A문서는 3번째에 출력되는 것을 알 수 있다.