[파이썬] 1966번: 프린터 큐

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

1966번: 프린터 큐

 

생각했던 것만큼 잘 풀리지 않아 아래 링크를 참고했다. 

# 프린터 큐
for _ in range(int(input())):
    # N = 문서의 개수, M = 문서가 Queue에 놓인 순서
    N, M = map(int, input().split())
    
    # N개 문서의 중요도
    prec = list(map(int, input().split()))
    
    # 중요도 리스트의 인덱스 관리
    idx = list(range(N))
    idx[M] = 'target'
    
    # 문서가 출력될 순서
    order = 0

    while True:
        if prec[0] == max(prec):
            order += 1

            if idx[0] == 'target':
                print(order)
                break
            else:
                prec.pop(0)
                idx.pop(0)
        else:
            prec.append(prec.pop(0))
            idx.append(idx.pop(0))

참고링크: https://assaeunji.github.io/python/2020-05-04-bj1966/

 

문서의 중요도가 주어지면 그 중요도의 인덱스를 저장하는 idx 리스트도 만들어 인덱스와 중요도 리스트를 동시에 관리한다.

중요도 리스트는 FIFO로 인해 인덱스가 계속 변화하기에 M번째에 놓여 있던 문서가 몇 번째로 출력되는지 제대로 알기 어렵기 때문이다.

M번째에 놓여 있던 문서의 순서 변화도 관리하기 위해 인덱스를 저장하는 리스트를 따로 만든다.

 

가장 먼저 출력되어야 할 문서는 중요도가 가장 높은 문서, 즉 중요도 리스트의 최댓값이다.

그렇기에 최댓값이 리스트의 첫 번째에 올 때까지 FIFO를 수행한다.

최댓값이 첫번째에 오면 order에 1을 더하고 M번째 문서가 아니라면 그 문서를 출력했다는 의미로 리스트에서 팝한 후 남은 원소들 중의 최댓값이 맨 앞에 오도록 FIFO를 반복적으로 수행한다.

 

언젠가는 가장 큰 중요도의 문서가 큐의 M번째에 놓여 있던 문서가 되는 때가 온다.

그 때에는 order를 출력하고 반복문을 종료한다.