[BOJ] 1966. 프린터 큐

1. 해결방법

"""
1. 아이디어
- 입력 받은 문서의 개수 만큼 큐를 생성
- m을 -1만큼 돌면서 큐를 pop하며 우선순위가 높은 원소 값을 찾는다.
- pop으로 제거된 숫자의 우선순위가 크면 answer + 1을 하며 출력한다.
- 낮은 원소 값은 pop을 한 후 append를 통해서 맨 뒤로 이동.
- 원하는 문서가 뒤로 갈 때, m의 값도 큐 길이의 -1 만큼 초기화 해준다.

2. 시간복잡도
- O(T * N)

3. 자료구조
- while
- Queue
"""

 

 

2. 정답코드

입력 예제(1)

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

출력 예제(1)

1
2
5

 

코드

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

test = int(input())

for i in range(test):
    n, m = map(int, input().split())
    q = deque(list(map(int, input().split())))
    answer = 0
    while q:
        max_v = max(q)
        v = q.popleft()
        m -= 1
        if v == max_v:
            answer += 1
            if m < 0:
                print(answer)
                break
        else:
            q.append(v)
            if m < 0:
                m = len(q) - 1