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

문제 풀러 가기!!

큐, 구현 문제였다.!

큐를 두개 만들어서 풀었다.
하나는 문서 중요도들만 내림차순으로 담은 큐(1번 큐라고 하겠다), 하나는 tuple(문서 중요도, 문서 번호)로 묶어서 담은 큐(2번 큐라고 하겠다)! 처음 프린터 큐에서 M번째 문서를 몇 번째로 프린트했는지를 구하는 것이라서, 문서 번호(처음 프린터 큐에서 몇 번째로 위치하는지)를 저장해야 한다.

두번째 큐의 맨 앞에 있는 것을 뽑으면(popleft) 인쇄할 차례가 된 문서가 된다. 그 문서의 중요도가 그때 있는 문서들 중에서 가장 높으면(첫번째 큐의 맨 앞 원소를 확인하기), 프린트를 했다고 본다. 프린트를 했으면 첫번째 큐에서도, 두번째 큐에서도 맨 앞에 있는 원소를 빼주면 된다.
프린트를 하지 않으면, 두번째 큐의 맨 앞 원소만 빼서 맨 뒤로 보내준다.

import sys
from collections import deque

input = sys.stdin.readline
T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    origin_papers = list(map(int, input().split()))
    priority = deque(sorted(origin_papers, reverse=True))  # 중요도들 모음(높은 것부터)

    papers = deque()  # 문서 중요도, 문서 번호를 튜플 형태로 묶어서 저장
    for i in range(N):
        papers.append((origin_papers[i], i))

    print_cnt = 0  # 인쇄 순서
    while papers:
        tmp_paper_priority, tmp_paper_idx = papers.popleft()  # 이번 차례 문서의 중요도, 원래 위치
        now_paper_priority = priority[0]  # 이번 차례에 인쇄할 문서의 중요도

        if tmp_paper_priority == now_paper_priority:  # 이 문서가 제일 높은 중요도 가지면
            print_cnt += 1  # 프린트
            priority.popleft()  # 그 중요도를 중요도 deque에서 제거
            if tmp_paper_idx == M:  # 몇번째로 인쇄되었는지 궁금한 문서이면
                print(print_cnt)  # 정답 출력
                break
        else:  # 이것보다 더 중요도가 높은 문서가 있으면
            papers.append((tmp_paper_priority, tmp_paper_idx))  # 그 문서를 차례의 마지막으로 보내기