알고리즘 문제 풀이
[백준 1966번] 프린터 큐 - 파이썬
진!!!!!
2024. 3. 23. 18:46
https://www.acmicpc.net/problem/1966
1966번: 프린터 큐
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에
www.acmicpc.net
💡문제 분석 요약
가장 중요한 문서를 먼저 프린터하고, 현재 문서보다 더 중요한 문서가 있을 경우 현재 문서를 맨 뒤 순서로 보낸다.
내가 원하는 문서는 몇번째로 출력되는가?
💡알고리즘 설계
1. 현재 문서 리스트에서 가장 중요도가 높은 문서의 중요도를 구한다.
2. 현재 문서보다 더 중요한 문서가 있을 경우, 현재 문서를 제일 뒷 순서로 보낸다.
3. 현재 문서가 가장 중요한 문서일 경우, 문서를 프린터(popleft()) 한 후 프린트 횟수를 더한다.
4. 내가 원하는 문서의 순서가 0번째이고, 이 문서의 중요도가 가장 높을 경우, 프린트 횟수를 출력한다.
5. 문서가 프린트 되거나 뒷 순서로 이동될 때 마다 내 문서의 순서를 하나씩 줄여나가고, 내 문서가 맨 뒤로 이동했을 경우는 내 문서의 순서를 len(queue)-1로 설정한다.
💡코드
import sys
input = sys.stdin.readline
from collections import deque
T=int(input())
for _ in range(T):
N, M=map(int, input().split())
doc_list=list(map(int, input().split()))
queue=deque(doc_list)
answer=1
order=M
while True:
max_num=max(queue)
if order==0 and queue[0]==max_num:
print(answer)
break
elif queue[0]<max_num:
queue.append(queue.popleft())
else:
queue.popleft()
answer+=1
if order>0: #알고싶은 문서의 현재 순서
order-=1
else:
order=len(queue)-1
💡 느낀점 or 기억할 정보
내 문서의 순서를 order로 관리하는 아이디어를 떠올리는게 중요한 것 같다.