[백준] 1966 | 프린터 큐 [파이썬/python]

문제

link: https://www.acmicpc.net/problem/1966

 

접근

collections의 deque를 사용해 deque를 만든 후, rotate를 이용해 큐를 회전해가며 중요도가 높은 순으로 출력하도록 했다. 

M번째 인덱스의 값이 언제 출력되는지를 확인해야 하므로, 초기 인덱스를 함께 저장했다.

rotate()에 음수를 넣을 경우 왼쪽으로, 양수를 넣을 경우 오른쪽으로 회전한다. 값을 꺼낼 때는 popleft()로 0번째 인덱스 값을 꺼내고, rotate(-1)로 왼쪽 방향으로 회전시키며 중요도를 비교했다.

 

코드

import sys
input = sys.stdin.readline
from collections import deque

for _ in range(int(input())):
    N, M = map(int, input().split())
    imp = list(map(int, input().split()))
    impq = deque([i, imp[i]] for i in range(N))
    imp.sort(reverse=1)
    i = 0
    
    while 1:
        if impq[0][1] == imp[i]:
            tmp = impq.popleft()[0]
            if tmp == M:
                print(i + 1)
                break
            i += 1
        else:
            impq.rotate(-1)