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

백준 1966 - 프린터 큐

---

* 풀이 과정

파이썬의 deque를 이용하여, 큐를 구현하는 문제이다.

deque 활용은 처음이었고, 무엇보다 문제에서 주어진 인덱스에 해당하는 값의 출력 순서를 알아야 하는데, 해당 값의 인덱스가 계속 변한다는 점을 해결하지 못해서 결국 다른 풀이를 참고했다.

 

연산에 따라 인덱스가 변경한다면, 구해야 하는 인덱스 값도 그에 맞춰서 변경해주면 되는 것....

알고보니 굉장히 간단한 방법...

 

이 문제에서, M(=인덱스)에 위치한 값의 출력 순서를 구해야 한다.

1) 중요도가 저장되어 있는 배열에서 가장 큰 중요도, 0번 인덱스에 위치한 값을 각각 뽑는다. (0번 인덱스에 위치한 값은 deque의 popleft() 내장함수 이용하여, 우선 배열에서 제거)

2-1) 위 두 값이 다르다면, 0번 인덱스에 위치한 값을 배열의 끝에 다시 넣어주고(append), M도 앞으로 이동해야 하므로 M-1 처리한다.

2-2) 앞으로 이동한 M의 값이 0보다 작다면, 이미 가장 앞에 위치하고 있었다는 뜻이므로, 가장 끝의 인덱스로 변경한다.

3-1) 위 두 값이 같다면, 0번 인덱스에 위치한 값은 제거된 상태 그대로 유지하고, M도 앞으로 이동해야 하므로 M-1 처리해준다.

3-2) 앞으로 이동한 M의 값이 0보다 작다면, 이미 가장 앞에 위치하고 있었다는 뜻이므로, cnt를 출력하고 반복문을 break.

from collections import deque
import sys

T = int(input())
    
for _ in range(T):
    N, M = map(int, input().split())
    queue = deque(list(map(int, sys.stdin.readline().split())))
    cnt = 0
    while True:
        maxValue = max(queue)
        front = queue.popleft()
        M -= 1
        if front != maxValue:
            queue.append(front)
            if M < 0:
                M = len(queue) - 1
        else:
            cnt += 1
            if M < 0:
                print(cnt)
                break

 

참고 풀이

https://hongcoding.tistory.com/42