문제
https://www.acmicpc.net/problem/1966
풀이
생각보다 푸는 데 오래 걸려서 당황한 문제..👿
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
쉽게 이해하자면 가장 앞에 있는(인쇄하려는) 문서의 중요도가 가장 높지 않으면 뒤로 재배치한다.
가장 앞에 있는 문서의 중요도가 가장 높다면 인쇄한다.
가장 앞에 있는 값을 뒤로 재배치할 때 pop(0) 대신 deque의 popleft()를 이용하면 수행시간을 줄일 수 있다❗️
코드 및 해설
from collections import deque
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n,m = map(int,input().split()) # 문서의 개수, 알고 싶은 값의 인덱스
queue = deque(map(int,input().split())) # 저장하려는 deque 선언
cnt = 0 # 인쇄된 횟수
while queue:
output = max(queue) # 중요도가 가장 높은 값
first = queue.popleft() # 가장 앞에 있는 값
m -= 1 # queue의 인덱스 값을 맞춰주기 위해 -1
if output == first: # 가장 앞에 있는 값이 중요도가 가장 높은 값일 때
cnt += 1 # 인쇄
if m < 0: # 인쇄한 값이 내가 알고 싶은 값이면
print(cnt) # 인쇄된 횟수 출력
break
else: # 가장 앞에 있는 값이 중요도가 가장 높은 값이 아닐 때
queue.append(first) # 가장 앞에 있는 값을 뒤로 재배치
if m < 0: # 뒤로 보낸 값이 내가 결과를 원하는 값일 때
m = len(queue) - 1 # 인덱스 값을 가장 끝으로 변경참고
if output == first에서 내가 알고 싶은 값이 아닌 다른 값(m>0)이 출력되면 first = queue.popleft()로 인해 그 값은 사라집니다.
