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

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

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

1966번: 프린터 큐

실버3

구현 자료구조 시뮬레이션 큐

---

실버3 치고는 상대적으로 쉽고 정답률도 높은 문제였다. 큐를 이용한 문제이므로 FIFO 방식으로 정렬해야한다.

맨 왼쪽을 기준으로 중요도가 가장 큰 값이 아니면 맨 오른쪽으로 보내고, 중요도가 가장 큰 값일때는 값을 제거해야 한다. 값을 제거할 때만 특정 변수의 값을 증가시켜 원하는 인덱스의 값이 빠질 때 특정 변수의 값을 출력한다.

 

코드(88ms)

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    lev = deque(map(int, input().split()))
    dq = deque(['B']*N)
    dq[M] = 'A'
    pcnt = 0
    while True:
        maxx = max(lev)
        while lev[0] < maxx:
            p = lev.popleft()
            p1 = dq.popleft()
            lev.append(p)
            dq.append(p1)
            
        if lev[0] == maxx:
            lev.popleft()
            a = dq.popleft()
            pcnt += 1
            if a == 'A':
                print(pcnt)
                break

 

중요도를 입력한 리스트를 그대로 본딴 덱을 하나 만들고, 필요한 인덱스 값에 A를, 나머지 값에는 모두 B라는 값을 주었다.

 

중요도 리스트의 max값 전까지 한번에 popleft와 append를 반복해주고, max값과 일치할 때는 popleft만 진행하고 pcnt를 1씩 올려준다. 만약 여기서 뺀 값이 A와 같다는 것은 문제에서 필요한 인덱스의 값을 뽑아낸 것과 같으므로 pcnt값을 출력하며 반복문을 종료한다.

 

 

다른 사람 코드(100ms)

 

from collections import deque
import sys

t = int(input())

for i in range(t):
    n, m = map(int, input().split())
    queue = deque(list(map(int, sys.stdin.readline().split())))
    count = 0
    while queue:
        best = max(queue)  #현재의 최댓값이 가장 먼저 배출되므로 최댓값을 저장
        front = queue.popleft() # 큐의 front를 뽑았으므로
        m -= 1 # 내 위치가 한 칸 당겨진다.

        if best == front: # 뽑은 숫자가 제일 큰 숫자일 때
            count += 1 # 하나가 영원히 배출되므로 순번 하나 추가
            if m < 0: # m이 0이라는 것은 뽑은 숫자가 내 숫자라는 뜻.
                print(count)
                break

        else:   # 뽑은 숫자가 제일 큰 숫자가 아니면
            queue.append(front) # 제일 뒤로 밀려나게 됨
            if m < 0 :  # 제일 앞에서 뽑히면
                m = len(queue) - 1 # 제일 뒤로 이동

출력해야 할 인덱스를 m을 입력받은 후, queue의 front값을 뽑았을 때 한 칸 앞으로 조절한다.

뽑은 값이 중요도가 가장 큰 숫자라면 count를 올리고, m이 0다 작으면 필요한 인덱스 값을 뽑은 것이므로 count값을 출력한다.

뽑았던 값이 중요도가 가장 큰 숫자가 아니라면 큐의 맨 마지막에 다시 삽입한다.

만약 m이 0보다 작은 상황이라면 인덱스 값을 잘못 뽑은 것이므로 m을 큐의 마지막 위치로 설정한다.