알고리즘 문제 풀이

[백준 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로 관리하는 아이디어를 떠올리는게 중요한 것 같다.