[백준] 1966번: 프린터 큐

문제에 나온 그대로 큐에 push와 pop을 일일히 다 적용하면서 구하면 또 시간초과가 뜰 것 같아서 다른 방법을 생각해보기로 했다.

큐의 가장 앞에 있는 항목을 맨 뒤로 보내고, 그 다음 항목도 맨 뒤로 보내고...를 반복하다 보면 결국 큐는 처음 상태와 같아진다. 항목 간의 위치 변화가 없는 것이다.
이것을 순회하는 입장에서 생각하면 큐를 처음부터 끝까지 순회한 후 다시 처음으로 돌아가 반복하는 것과 같다.

우선순위 큐를 입력받을 때, 각 우선순위 항목의 개수도 함께 받아놓는다.
가장 큰 우선순위인 9부터 1까지 내림차순으로, 해당 우선순위의 문서를 다 셀 때까지 큐를 반복 순회하며 지금까지 센 문서 개수 (count)를 증가시킨다.
목표로 한 우선순위를 셀 차례가 되었을 때 현재 인덱스와 목표 인덱스가 같다면 count + 1을 출력한다.

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    priority = [0] * 10
    queue = list(map(int, input().split()))

    for i in queue:
        priority[i] += 1

    idx = 0
    count = 0
    isBreak = False
    for i in range(1, 10):
        while priority[10 - i] > 0:
            if idx == M and 10 - i == queue[M]:
                print(count + 1)
                isBreak = True
                break
            if queue[idx] == 10 - i:
                priority[10 - i] -= 1
                count += 1
            idx = (idx + 1) % N
        if isBreak:
            break