백준 1966번 풀이
큐 실습 예제로 찾은 문제입니다. _(실버 III)
문제 내용
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 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번째로 인쇄되게 된다.
조건
첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)
몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M이다. M(0 ≤ M < N) 이때 맨 왼쪽은 0번째로 한다.두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
시간제한: 2초
메모리제한: 128MB
풀이 과정
문제 이해
해당 내용은 문제 이해가 가장 어려운 부분이었습니다.
우선 입력만 두고 보면, 맨 첫번째 입력은 Test 횟수입니다.
이후부터는 각 Test에 따른 경우인데, 1번째 줄은 N, M을 각각 입력하고, 2번째 줄은 문서의 우선 순위를 나열합니다.
N : 문서의 개수
M : 프린터에 들어간 것중 몇 번째 문서인지
이제 우선 순위를 통해 Queue에서 뽑아 M이 가리킨 문서가 뽑힌다면 그 순서를 출력합니다.
과정 풀이 1
test를 입력받은 후test만큼 반복을 시작합니다.N, M그리고 우선 순위 List인priority를 받습니다.priority에 대한 것을printer로 생성한 Queue에 넣습니다.- 몇 번째에 출력이 됐는지 출력을 위한
count변수를 지정합니다. while True:로 하나의 프린터를 시작합니다.printer[-1]은 Queue의 front를 가리키므로 이것이max(printer)라면 pop()을 시키며count++을 진행합니다.
6-1. 위 경우가 아니라면 중요도가 낮은 Queue에 front를pop()시켜서 다시 Queue의 rear로 넣습니다.
위 과정까지 진행하던 중 M에 대한 위치를 나타내는 것에 어려움을 느꼈습니다.
과정 풀이 2
Queue에 우선순위를 넣어서 진행하다보니 M에 대한 위치를 표현하는 것이 어려웠습니다. Queue는 계속해서 변화하는데 변화하는 Index를 따라가는거에 대한 문제점이 있었습니다.
해당 내용을 고민하다가 Index를 말 그대로 M이 따라가면 할 수 있지않을까 해서 그렇게 문제를 해결 했습니다.
위 풀이를 이어 가자면
7. printer[-1] == max(printer) 이면서 M == 0인 경우 M을 출력한 것으로 판단하여 출력 종료
8. 위 한 Cycle을 돈 뒤 M--하며 Queue에 우선순위대로 반복하며 빼기
정답
from collections import deque
import sys
input = sys.stdin.readline
test = int(input())
printer = deque()
for i in range(0, test):
N, M = map(int, input().split())
priority = list(map(int, input().split()))
for j in range(0, len(priority)):
printer.appendleft(priority[j])
count = 1
while True:
if printer[-1] == max(printer) and M == 0:
print(count)
break
if printer[-1] == max(printer):
printer.pop()
count += 1
else:
temp = printer.pop()
printer.appendleft(temp)
M -= 1
if M < 0:
M = len(printer) - 1
printer.clear()
위 코드를 통해 성공했다.
(시도: 1, 정답: 1)
달성 조건
| Language | Memory | Time |
|---|---|---|
| Python3 | 34140 KB | 108 ms |
