[BOJ] 1966 프린터 큐

[백준]1966 문제링크

예제의 두 번째 테스트 케이스를 토대로 해석해 보자면
4개의 문서 중 인덱스 2에 해당하는 인쇄물이 몇번째로 출력되느냐를 묻는 내용이다.
priority 리스트는 [1, 2, 3, 4, 5]로 계산을 하면 된다.

리스트에서 하나씩 꺼내서 그 priority보다 더 큰 수가 있다면 뒤로 보내고, 없다면 프린트 한다

queue를 만들어서 인덱스와 값을 저장해두는 방식으로 풀었다.
처음에는 인덱스만 저장한 다음 priority 리스트에서 값만 확인을 했었는데
그렇게 하면 사용한 값은 초기화를 해줘야한다
지금 생각해보면 값을 0으로 초기화해서 계산하면 큐에 인덱스만 넣어서 계산해도 값이 나올 것 같다

1. queue에 모든 값을 튜플 형태로 넣어준다. ( idx, priority[idx] )
2. queue에 값이 존재하는 동안 while loop를 돈다.
   2-1. pop한 값과 queue에 존재하는 다른 값들을 전부 비교해서 더 큰 값이 있으면 뒤에 추가해준다.
   2-2. 큰 값이 없다면, 프린팅을 해준다.
   2-3. 큰 값이 없으면서, idx가 찾는 인쇄물과 갖다면 반복문을 빠져나와서 프린팅을 출력한다.

[github] 1966 해결 코드

import sys
from collections import deque
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    priority = list(map(int,input().split()))
    queue = deque((i,priority[i]) for i in range(n))
    printing = 0
    while queue:
        idx,num= queue.popleft()
        a = 0
        for x,y in queue:
            if num < y:
                a=1
                break
        if a==0:
            printing+=1
            if idx == m:
                print(printing)
                break
        else:queue.append((idx,num))

queue 에 index만 넣었을 때와 비교해보면

생각보다 시간차가 나지 않는다 헤헷