[백준]1966번 프린터 큐 - 큐

 

from collections import deque

n = int(input())

for i in range(n):
    queue = deque([])
    num, wh = map(int, input().split())
    temp = (list(map(int, input().split())))
    for i in range(len(temp)):
        queue.append(temp[i])

    temp[wh] = 'answer'
    cnt = 0
    while True:
        if queue[0] == max(queue): # 큐의 맨 앞자리가 우선순위가 제일 높은 경우
            cnt = cnt + 1 # 카운트
            if temp[0] == 'answer': # 지정한 인덱스가 맞을 경우
                print(cnt) # 출력
                break
            else: # 우선순위는 제일 높지만, 지정한 인덱스가 아닐 경우
                queue.popleft() # 제일 높은 우선순위이기 때문에 큐에서 삭제만 해도 됨 (뒤로 넣을 필요x)
                temp.pop(0)
        else: # 우선순위가 낮으므로, 큐의 맨 뒤로 이동
            queue.append(queue.popleft())
            temp.append(temp.pop(0))

 

코드 설명

문서의 개수를 num, 궁금한 위치를 wh 변수에 입력받아 저장한다. 그 후 temp 리스트에 문서의 중요도를 저장한다. 문서의 개수만큼 반복하여 문서의 중요도를 큐에 초기화 시켜준다. temp 리스트의 궁금한 위치의 원소는 'answer' 로 바꾼다.

반복문을 진행하면서 큐의 맨 앞에 존재한 원소가 우선순위가 가장 높을 경우에는 카운트를 해주고, 그 문서가 'answer' 라면 출력하고 끝마친다. 그렇지 않다면 큐와 temp 리스트에서 원소를 삭제한다.

만약 우선순위가 제일 높지 않을 경우에는 원소를 뽑아 큐의 뒤로 보낸다.

 

Point: 처음에는 우선순위 큐(Priority Queue)를 사용하였으나 뒤로 보내는 문제가 발생하여 일반적인 큐로 해결하였다.

우선순위가 제일 높은 숫자일 때, 그것이 궁금한 문서라면 카운트 수를 출력, 아니라면 큐에서 제거한다.

우선순위가 제일 높지 않을 경우, 큐의 뒤로보내 우선순위를 맨 뒤로 만든다.