2022.02.25 [백준] (python 파이썬) 프린터 큐

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

1966번: 프린터 큐

---

풀이

해당 문제는 입력 받은 문서 중, 제일 앞에 있는 문서의 중요도가 뒤에 위치한 문서의 중요도보다 낮으면 해당 문서를 뒤로 보내야한다. 그래서 양방향 입출력이 가능한 deque을 이용하여 코드를 작성했다.

문서를 deq에 저장할 때, 각 문서가 입력된 순서와 중요도를 (중요도, 입력된 순서)로 저장해서 중요도 순으로 프린트할 때, 원하는 순서의 문서가 몇번째로 출력되는지 체크했다. 

또한 제일 앞에 위치한 문서의 중요도를 뒤에 있는 문서들의 중요도와 비교하여 중요도가 더 높은 문서가 있다면 빼서 뒤에 넣어야한다.

이 작업을 만약 뒤에 더 큰 중요도가 발견되자마자 뒤로 보내면 이중for문을 써야한다고 생각해서, 코드에선 for문을 돌면서 가장 큰 중요도를 가진 문서를 x,y의 변수에 중요도, 문서의 입력순서로 저장했다. 

그래서 for문이 모두 돌고 가장 큰 중요도를 가진 문서의 값이 변수에 저장되면 deq.index를 이용해 해당 값이 몇번째 인덱스에 위치한지 찾았다. 다음 deq.rotate를 이용해 인덱스 값만큼 왼쪽으로 회전시켜주었다.

그러면 가장 큰 중요도를 가진 문서가 제일 앞에 위치하고 해당 값을 popleft를 이용해 뽑아 낸다음 문서의 입력순서가 문제에서 알고싶어하는 순서인지 확인했다. 그리고 cnt를 증가시켜 몇번째에 출력되는지를 체크했다.

from collections import deque
 
T=int(input())
for _ in range(T):
    n,m=map(int, input().split())
    deq=deque()
    arr=list(map(int, input().split()))
    for i in range(n):
        deq.append((arr[i],i))
    cnt=1
    while deq:
        x,y=deq[0]
        for i in range(len(deq)):
            if x<deq[i][0]:
                x,y=deq[i]
        deq.rotate(-deq.index((x,y)))
        deq.popleft()
        if y==m:
            print(cnt)
            break
        cnt+=1