[백준 1966] 프린터큐

문제 요약

프린터 큐는 인쇄할 문서를 고를 때 기본적으로 FIFO원칙을 따르지만 다음과 같은 규칙을 가집니다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

각 테스트케이스의 인풋

첫번째 줄에 문서의 개수 n, 몇 번째로 출력되는지 궁금한 문서의 번호 m이 한 줄에 입력됨.
두번째 줄에 각 문서들의 priority가 입력됨.

아웃풋

m 번째 문서의 출력 순서

아이디어

queue를 활용한 시뮬레이션이 필요하다.

샛길

priority queue를 사용해서 첫번째 우선순위를 중요도, 두번째 우선순위를 인덱스로 했을 때 2번 경우에 해당해서 인쇄를 보류하는 일을 하지 않아도 될 거라고 생각했었다.

그렇게 했을 때 우선순위에 따라 중요도가 높은 문서가 우선적으로 수행되는 건 맞다. 그렇지만 중요도가 같은 문서들 중에선 시뮬레이션 하는 것처럼 순서가 정확하지 않다. 문제 설명에서 큐로 시뮬레이션할 때 앞에 있던 게 다시 뒤로 가면서 인덱스 순서가 유지될 거같지만 앞쪽 인덱스가 뒤로 숨어버린 거 때문에 뒤쪽 인덱스가 먼저 나올 수 있기 때문이다.

(4,C) (5,D) (4,E)
(5,D) (4,E) (4,C)
(4,E) (4,C)
(4,E) (4,C)

새로 배운 것

max 함수

python의 장점은 c++에서 간단한 함수라도 직접 구현하게 되는 것과 달리 내장함수로 구현이 돼있다는 것이다.

큐 안의 최대값을 구할 때 이번에 deque를 써서 사용해보진 못했지만 일반적으로 리스트 큐 & max(리스트)를 사용하는 것 같았다.

python의 reference 타입의 복사

큐의 최대값을 뽑는 함수, 큐의 내용물을 뽑는 함수(디버깅 용)를 구현했다.
tempq = q를 했을 때 c++에선 tempq가 독립적으로 메모리를 deep copy하지만 python은 tempq와 q가 레퍼런스를 공유한다.(함수호출 인자 전달도 마찬가지이다.)

import copy
tempq = copy.deepcopy(q)
max_p = get_max(tempq) #새로 객체 만들어야할 수 있음

queue 객체

소스코드

from collections import deque
import copy
def get_max(q):
    max_p = 0
    while q:
        cur = q.popleft()
        if max_p< cur[0]: max_p = cur[0]
    return max_p

t = int(input())
for ctr  in range(t):
    # 그대로 시뮬레이션
    ans = 0
    n , m = map(int,input().split())
    arr = list(map(int, input().split()))

    for i in range(n):
        arr[i] = (arr[i],i)

    visited = [-1 for i in range(n)]
    q = deque(arr)
    #print(len(q),len(arr))
    ctr =1
    while q:
        qf = q.popleft()

        tempq = copy.deepcopy(q)
        max_p = get_max(tempq) #새로 객체 만들어야할 수 있음
        #print("after getmax",max_p,len(q))

        if max_p>qf[0]:
            #print("1. 다시 넣는다 ", qf)
            q.append(qf)
        else:
            if qf[1] == m:
                print(ctr)
                break
            ctr+=1
        #tempq = copy.deepcopy(q)
        #print_q(ctr,tempq)