[큐] 백준 #1966 프린터 큐 - Python

🗂️ 문제

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

 

💡 접근법

제일 왼쪽의 값을 쉽게 꺼내기 위해 deque를 사용한다.

 

문서가 몇 번째로 인쇄되는지 횟수를 세기 위해 인덱스를 저장해야 한다. 이를 위해 queue에 튜플 형식으로 (인덱스, 중요도)를 저장한다.

while()문을 통해 큐에서 왼쪽에 위치한 값을 하나씩 꺼내고, 만약 그 다음 값들 중 현재 값보다 중요도가 높은 문서가 있다면 다시 큐에 현재 값을 삽입한다.

 

이때 인쇄가 될 경우 카운트 횟수를 증가시켜야 한다. 따라서 큐에서 현재 값을 꺼낼 때 카운트를 1 증가시키고, 만약 현재 값보다 중요도가 큰 문서를 발견하여 현재 값을 다시 큐에 삽입하게 되면 카운트를 1 감소시킨다.

 

target에 궁금한 문서를 저장해 두었다가, 큐에서 target이 빠져나갔을 경우, 즉 인쇄됐을 경우 while문을 빠져나온다.

 

😎 내 코드

import sys
from collections import deque

cnt = int(sys.stdin.readline())

for _ in range(cnt):
    N, M = map(int, sys.stdin.readline().split())
    que = list(map(int, sys.stdin.readline().split()))
    queue = deque()
    for i, q in enumerate(que):
        queue.append((i, q))  # (인덱스, 중요도)
    
    target = queue[M]
    count = 0
    while(queue):
        q = queue.popleft()

        count += 1
        for i in range(len(queue)):
            if queue[i][1] > q[1]:
                queue.append(q)
                count -= 1
                break
        
        if target not in queue:
            break

    print(count)

 

✅ 정답 확인