[백준] 1966번 프린터 큐 (Python 파이썬)

www.acmicpc.net/problem/1966

1966번: 프린터 큐

문제 설명

프린터는 FIFO(First In First Out) 즉 선입 선출의 구조로 문서를 출력하게 된다.

하지만 문제의 프린터에는 조건이 있다. 문서마다 중요도가 기록되어 있는데, 자신보다 중요도가 높은 문서가 하나라도 자신의 뒤에 있으면 자신은 맨 뒤로 밀려나게 된다.

 

예를 들어, A B C D 라는 4개의 문서의 중요도가 2 1 4 3이라면

2가 밀려나고 1이 밀려나고 4가 제일 먼저 출력되어 3 2 1 로 큐가 변경이 되며

여기서 또 3이 출력되고, 2가 출력되고 1이 출력된다.

 

문제의 각 케이스마다 자신이 설정한 문서가 몇 번째로 출력되는지를 구하면 된다.

---

풀이 과정

나의 숫자가 남은 큐 중에서 가장 큰 수가 될 때 까지 검사를 실시하면 된다.

그리고 자신의 문서의 인덱스를 m을 통해 변화를 주게 되며,

count를 통해 몇 번째로 빠져나갔는지 카운트하면 된다.

from collections import deque
import sys

t = int(input())

for i in range(t):
    n, m = map(int, input().split())
    queue = deque(list(map(int, sys.stdin.readline().split())))
    count = 0
    while queue:
        best = max(queue)  #현재의 최댓값이 가장 먼저 배출되므로 최댓값을 저장
        front = queue.popleft() # 큐의 front를 뽑았으므로
        m -= 1 # 내 위치가 한 칸 당겨진다.

        if best == front: # 뽑은 숫자가 제일 큰 숫자일 때
            count += 1 # 하나가 영원히 배출되므로 순번 하나 추가
            if m < 0: # m이 0이라는 것은 뽑은 숫자가 내 숫자라는 뜻.
                print(count)
                break

        else:   # 뽑은 숫자가 제일 큰 숫자가 아니면
            queue.append(front) # 제일 뒤로 밀려나게 됨
            if m < 0 :  # 제일 앞에서 뽑히면
                m = len(queue) - 1 # 제일 뒤로 이동

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !