백준 1966: 프린터 큐 Python

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

1966번: 프린터 큐

 

N(1 ≤ N ≤ 100), M(0 ≤ M < N)으로 입력이 크진 않지만 pop()을 써야 하기 때문에 deque를 활용해야 한다.

중요도가 같은 문서가 여러 개 있을 수도 있기 때문에, 중요도 입력 리스트에다가 인덱스를 함께 달아줬다.

(lst[i], i)와 같이 튜플 형태로 deque에 넣었다.

 

문제 해결 방식은 다음과 같다.

1. 인쇄되는 순서는 변수 cnt로 설정하고, 초기값을 0으로 둔다.
2. 먼저 lst[i], 즉 중요도를 기준으로 max 값을 찾는다.
3. queue의 맨 첫 번째 값의 중요도가 max 값 이상이면 큐에서 빼내야 하는데, 맨 첫 번째 값의 인덱스가 찾고 싶은 문서의 인덱스(=M)와 일치하면 cnt += 1을 해주고 반복문을 끝낸다.
4. 중요도가 max 값 이상인데 인덱스가 M과 일치하지 않으면 그 값을 빼내기고 cnt += 1을 한 채로 반복문을 계속한다.
5. 만약 중요도가 max 값 미만이라면 빼서 queue 뒤에 다시 넣는다.
6. queue 안에 있는 값 하나하나를 처리할 때마다 최대 가중치 값을 다시 계산해줘야 한다. 

from collections import deque


T = int(input())
for tc in range(T):
    N, M = map(int, input().split())    # N: 문서의 개수, M: 순서 찾을 문서
    lst = list(map(int, input().split()))
    q = deque()
    for i in range(N):
        q.append((lst[i], i))
    cnt = 0
    max_value = max(q, key=lambda x: x[0])

    while True:
        if q[0][0] >= max_value[0] and q[0][1] == M:
            cnt += 1
            break
        elif q[0][0] >= max_value[0]:
            q.popleft()
            cnt += 1
        else:
            q.append(q.popleft())
        max_value = max(q, key=lambda x: x[0])
    print(cnt)