[백준 파이썬 1966번 : 프린터 큐] 큐를 이용한 풀이

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

1966번: 프린터 큐

일반적인 큐 문제에 중요도라는 개념을 더해서 조금 복잡해졌다. 특히 중요도가 중복될 수 있기 때문에 주의가 필요하다. 

예시에서처럼 중요도로 1,1,9,1,1,1이 들어오면 '중요도가 1인 문서의 출력 순서'를 구하는 방법은 통하지 않기 때문이다 

 

나는 입력받은 큐를 que, 인덱스를 원소로 넣은 idx_que를 이용하여 풀었다.

que에 대한 푸시, 팝을 동일하게 idx_que에 적용하면 한 문서가 출력됐을 때(pop됐을 때)의 인덱스를 알 수 있기 때문이다 

그리고 백준 사이트의 큐, 스택 문제들은 리스트를 이용하여 풀 때 시간 초과가 자주 나오므로 deque 라이브러리를 이용하여 풀었다

 

1. que 로 문서의 중요도를 입력받는다 

2. idx_que에 인덱스를 입력해준다 

3. 큐의 첫 번째 요소가 큐의 최대값이라면 pop해준다. idx_que도 pop해준다

4. pop할 때마다 cnt로 몇 번째로 인쇄된 것인지를 카운트해준다 

5. 큐의 첫 번째 요소가 큐의 최대값이 아니라면 pop한 후 push해서 큐의 마지막으로 보내준다. idx_que에 대해서도 동일하게 처리한다 

6. idx_que에서 pop한 요소가 x(인쇄 순번을 구하는 문서)와 같다면 cnt를 출력해준다

 

from collections import deque 
t = int(input()) 
for _ in range(t):
    n , x = map(int,input().split())
    que = deque(list(map(int,input().split())))
    idx_que = deque(list(range(n)))
    cnt = 0 
    while que:
        if que[0] == max(que):
            cnt += 1
            que.popleft()
            if idx_que.popleft() == x:
                print(cnt)
        else:
            que.append(que.popleft())
            idx_que.append(idx_que.popleft())