[자료구조/큐] 백준 1966 프린터 큐 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1966번: 프린터 큐

 

 

 

2. 문제 풀이

 N개의 문서 중 M번째 문서가 출력되는 순서를 구합니다. 프린터 큐는 선입선출 방식으로 먼저 출력한 문서가 먼저 나옵니다. 하지만 이 문제에서는 문서마다 중요도가 있으며, 중요도가 제일 높은 문서만 출력됩니다. 중요도가 낮은 문서는 맨 뒤로 출력이 미뤄집니다.

 

2022.02.10 - [Algorithm] - [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

[Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

 조금 너무한 알고리즘입니다. 열심히 섰는데, 중요도가 낮아서 맨 뒤로 가라니요....

 어쨌든 큐 자료구조를 이해하고 있으면 쉽게 풀 수 있습니다. 맨 앞 문서의 중요도가 가장 클 때만 출력(pop)하고 높지 않으면 맨 뒤로 순서를 보냅니다. 출력할 때마다 횟수를 기록한 뒤, M 문서가 출력될 때 횟수를 구합니다.

 

 

 

3. 코드

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())
for i in range(T):
    N, M = map(int, input().split())
    printQueue = deque(list(map(int, input().split()))) #프린터 큐

    idx = deque(list(range(N))) # 인덱스
    idx[M] = 'M'

    cnt = 0 #뽑히는 순서
    while True:
        # 중요도가 가장 높으면 pop
        if printQueue[0] == max(printQueue):
            cnt += 1
            # 해당 문서가 M일 경우 종료
            if idx[0] == 'M':
                print(cnt)
                break
            # 아닐 경우 pop
            else:
                printQueue.popleft()
                idx.popleft()
        # 중요도가 높지 않을 경우 뒤로 보냄
        else:
            printQueue.append(printQueue.popleft())
            idx.append(idx.popleft())

 deque 라이브러리를 이용하면 쉽게 큐를 구현할 수 있습니다.

 문서 M의 위치를 기록하기 위해서 따로 인덱스 큐(idx)도 만들어 줍니다. 프린터 큐와 같이 push, pop하면서 M의 위치를 파악합니다.

 맨 앞 문서가 제일 중요도가 높으면 출력하고, 아니면 빼서(pop) 뒤로 보냅니다.(push)

 

 

import sys
input = sys.stdin.readline

T = int(input())
for i in range(T):
    N, M = map(int, input().split())
    printQueue = list(map(int, input().split())) #프린터 큐

    idx = list(range(N)) # 인덱스
    idx[M] = 'M'

    cnt = 0 #뽑히는 순서
    while True:
        # 중요도가 가장 높으면 pop
        if printQueue[0] == max(printQueue):
            cnt += 1
            # 해당 문서가 M일 경우 종료
            if idx[0] == 'M':
                print(cnt)
                break
            # 아닐 경우 pop
            else:
                printQueue.pop(0)
                idx.pop(0)
        # 중요도가 높지 않을 경우 뒤로 보냄
        else:
            printQueue.append(printQueue.pop(0))
            idx.append(idx.pop(0))

 deque 라이브러리를 이용하지 않고 리스트로만으로 구현할 수도 있습니다. popleft() 대신 pop(0)을 해주시면 됩니다.