[백준(BOJ)] 1966번 프린터 큐

문제

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

1966번: 프린터 큐

주어진 중요도에 따라 문서가 몇 번째로 인쇄되는지를 출력하는 문제다. 

예시

Example 1:

Input : 3
	1 0
	5
	4 2
	1 2 3 4
	6 0
	1 1 9 1 1 1
Output : 1
	2
	5

풀이

from collections import deque

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())

    queue = deque(map(int, input().split()))
    queue = deque([(value, idx) for idx, value in enumerate(queue)])

    count = 0

    while True:
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            count += 1
            if queue[0][1] == m:
                print(count)
                break
            else:
                queue.popleft()
        else:
            queue.append(queue.popleft())

 

- 큐 자료구조를 사용하여 문서의 중요도에 따라 몇 번째로 출력되는지를 계산한다.

- 문서의 중요도를 입력받아 데크로 변환하고 중요도와 인덱스를 튜플로 묶어 저장한다.

- 가장 앞에 있는 문서의 중요도가 큐에서 가장 높은 중요도와 같은지 확인하고 같다면 인쇄 횟수(count)를 증가시킨다.

- 현재 출력된 문서가 궁금한 문서라면 인쇄 횟수를 출력하고 아니라면 큐의 가장 앞 문서를 제거한다.

- 가장 앞에 있는 문서의 중요도가 큐에서 가장 높은 중요도와 다르다면 큐의 뒤로 옮긴다.

- 위의 방법을 궁금한 문서가 인쇄될 때까지 반복하면 몇 번째로 출력되는지 구할 수 있다.