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

 

 

"""
- 자료구조 큐 사용

* 문제 정리
- 출력값 : 각 문서의 중요도와 순서에 따라 인쇄가 될때, N개중 M번째의 문서는 몇번째로 출력되는가?
- 인쇄 조건
- 현재 큐의 가장 앞에 있는(0번째) 문서의 중요도 확인
    - 다른 문서들 중 중요도가 더 높은것이 있는지?(= 현재 문서의 중요도가 가장 높은지?)
    - 더 높은 것이 없다면 출력
    - 그렇지 않다면 맨 뒤로 재배치
    - 0번째 문서의 중요도 확인 반복

* 수도 코드
- 중요도들을 큐에 추가
- 찾을 문서의 현재 위치를 기억
- 인쇄 조건 확인 => 0번째 문서가 중요도의 최대값과 같은지?
- 같다면 출력 + 1. 찾을 위치값 -1.
- 다르다면 0번째 문서를 제거 후 맨 뒤에 다시 추가. 찾을 문서의 위치값 조정.
- 찾을 문서의 위치값이 0이 되었을때 출력이 된다면 + 1. 출력값을 리턴.

메모리 34044KB | 시간 76ms | 길이 837B
"""
from collections import deque
case_num = int(input())
m_ls = []
importance_ls = []

for _ in range(case_num):
    _, m = map(int, input().split())
    m_ls.append(m)
    importance_ls.append(input().split())

def check_order(m, importance_ls):
    deck = deque()
    for i in importance_ls: # 중요도를 큐에 추가
        deck.append(i)
    print_cnt = 0 # 출력 횟수
    m_import = importance_ls[m] # m의 중요도 확인
    m_idx = m # m의 현재 위치
    while m_idx >= 0: # m이 0번째에 올때까지 반복
        most_import = max(deck) # 현재 가장 높은 중요도
        if deck[0] == most_import: # 0번째 문서의 중요도가 가장 높다면
            print_cnt += 1 # 출력
            deck.popleft() # 프린트 되었으니 0번째 제거
            m_idx -= 1 # 인덱스 1칸 당기기
        else:
            if deck[0] == m_import and m_idx == 0: # 만약 0번째가 m일경우(중요도와 현재 위치를 통해 찾고자 하는 문서인지 체크)
                m_idx = len(deck) - 1 # m을 맨 뒤로 보내고 현재 인덱스 수정
            else: # 그렇지 않을 경우 맨 앞 요소가 빠졌으니 m 인덱스 1칸 당기기
                m_idx -= 1
            deck.append(deck.popleft()) # 맨 앞 요소를 맨 뒤로 보내기
    return print_cnt # 반복문 종료후 프린트 된 개수 반환


for i in range(case_num):
    print(check_order(m_ls[i], importance_ls[i]))

 

 

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

1966번: 프린터 큐