[백준] 1966 (프린터 큐)

1966번: 프린터 큐

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
for _ in range(N):
    l, paper = map(int,input().split())
    dq = deque(map(int,input().split(' ')))
    done = 0
    i = 0    
    
    while True : 
        if i+1 == len(dq):
            if paper == 0:
                print(done+1)
                break
            else:
                dq.popleft()
                paper -= 1
                done += 1
                i = 0
                print('now : ', dq,paper)
                
        if len(dq) == 1 : 
            print(done+1)
            break
            
        if dq[0] >= dq[i+1]:
            i += 1
        else: 
            dq.append(dq.popleft())
            if paper == 0 : 
                paper = len(dq)-1
            else: 
                paper -= 1
            print(dq,paper)
            i = 0

# 출력 예시 
-- 입력 --
6 0 
1 1 9 1 1 1

-- 출력 --
deque가 회전될 때 마다 혹은 popleft될 때 마다 paper의 위치 표시 
deque([1, 9, 1, 1, 1, 1]) 5
deque([9, 1, 1, 1, 1, 1]) 4
now :  deque([1, 1, 1, 1, 1]) 3
now :  deque([1, 1, 1, 1]) 2
now :  deque([1, 1, 1]) 1
now :  deque([1, 1]) 0

-- 답 --
5

🗯️풀이 설명

고려했던 부분은 우선순위가 낮은 문서를 뒤로 보낼 때, 알고자하는 문서의 위치를 어떻게 변화시켜주는가 였다.

나는 paper 변수로 알고자하는 문서의 인덱스 값을 저장하여, 문서 dq의 순서가 변할 때 마다 paper 값을 변화시켜주었다. 

작동 과정을 시각적으로 나타내보았다.  분홍색 하이라이트가 된 문서가 출력 순서를 알고자하는 문서이다. 즉, paper 변수이다.

0번 문서와 그 뒤의 문서의 중요도를 한 개씩 비교하면서 0번 문서보다 중요도가 큰 문서가 있을 경우 0번 문서를 맨뒤로 보내고,

0번 문서 보다 중요도가 큰 문서가 없을 경우 0번 문서를 프린트한다. 

이 과정에서 분홍색 문서의 인덱스가 계속 변화하는 것을 알 수 있다. 따라서 paper = = 0 이 될 때 까지 알고리즘이 작동한다. 

👀 반례 

2
9 3
4 3 2 2 3 5 2 1 3
4 1
2 1 4 3

# 7
# 4



1
100 0
1 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 5 5 5 5 5 5 5 5 5 5

# 100

💡다른 풀이

뿌기님의 풀이가 더 맘에 들어서 가지고 왔당

from collections import deque

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    pop_num = []

    queue = deque([i+1 for i in range(n)])
    find_num = queue[m]
    imp_q = deque(map(int, input().split()))

    while True:
        if len(imp_q) == 0 :
            break
    
        max_idx = imp_q.index(max(imp_q))

        if max_idx != 0:
            queue.rotate(-1)
            imp_q.rotate(-1)
            continue

        elif max_idx == 0:
            pop_num.append(queue.popleft())
            imp_q.popleft()
            continue

    for num in pop_num :
        if find_num == num :
            print(pop_num.index(num) + 1)

deque 에 rotate 기능이 있는지 덕분에 알게 되었다 ..ㅎ 언니는 내가 코드 가져온거 모르겠지....ㅎ