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

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

1966번: 프린터 큐

접근 방식

- 효율적인 반복문 구성 방법 고민

- 큐 활용방법 고민

 

코드 풀이

from collections import deque
t = int(input()) # 테스트케이스 수

for _ in range(t):
    n, m = map(int, input().split()) # 문서의 수, 궁금한 책이 현재 있는 위치
    query_book = m+1 # 궁금한 책의 번호
    
    deq = deque()
    imp_list = list(map(int, input().split())) # 중요도를 리스트로 저장
     
    for i in range(n):
        deq.append([i+1, imp_list[i]]) # deque에 책 번호와 중요도 순서대로 저장
        
    answer = [] # 인쇄 문서번호를 순서대로 저장
    
    while deq:
        book_n, book_i = deq.popleft()

        if any(book_i<x[1] for x in deq): # deq에 남아 있는 책들 중 중요도가 하나라도 높은게 있다면
            deq.append([book_n, book_i]) # 다시 deq에 append
        else:
            answer.append(book_n) # 현재 인쇄 대기문서가 가장 큰 우선순위라면, 인쇄 진행
            if book_n == query_book: # 이때 문서번호가 궁금한 책의 번호와 일치한다면
                print(answer.index(book_n) + 1) # 해당 문서의 인덱스(순서)에 1 더해 출력

데크를 활용해 인쇄문서 대기열을 표현하였습니다. 데크에는 문서의 번호와 문서의 중요도가 튜플 형태로 묶여 들어가도록 했으며, popleft() 할때마다 대기열 안에 더 높은 중요도를 가지는 문서가 남아있는지 검사했습니다. 남아있는 경우 다시 데크에 오른쪽으로 추가해줬으며 그렇지 않은 경우에는 answer 리스트에 추가함으로써 인쇄 표기했습니다. 처음에 m의 정의를 '궁금한 책이 현재 있는 위치'가 아닌 '궁금한 책의 번호'라고 생각해 시간이 오래 소요됐습니다.

 

메모

- if any( x 조건식 for x in list)를 통해 코드 간단히 쓸 수 있습니다.

- 리스트 내의 특정 원소가 몇 번째 인덱스인지 출력하려면, list.index('a') 를 이용합니다.

 

참고

원소를 활용하여 인덱스를 찾는 두 가지 방법

import numpy as np

# 1. 리스트 활용
list_a = [4, 3, 2, 1, 1]
list_a.index(1) # 출력값: 3 (중복시 첫번째 값만 출력)

# 2. 어레이 활용
array_a = np.array(list_a) # array([4, 3, 2, 1])
np.where(array_a == 1) # 출력값: 3, 4 (중복 모두 출력)