백준 1966(프린터 큐) - Python(파이썬) - 큐,자료구조

1966번: 프린터 큐

예제 풀이

마지막 테스트케이스 :

priority:  (몇번째 숫자인지, 중요도)
( 0,1 )	( 1,1 )	( 2,9 )	( 3,1 )	( 4,1 )	( 5,1 )

sort_priorty: 중요도를 정렬시킨 리스트
9	1	1	1	1	1

priority[0][1] 와 sort_priority[0] 을 비교한다.

① priority[0][1] = 1 이 sort_priority[0] =9와 다름

=> priorirty[0][1]의 값을 popleft()하고 뒤에 append함

priority:  (몇번째 숫자인지, 중요도)
( 1,1 )	( 2,9 )	( 3,1 )	( 4,1 )	( 5,1 )	( 0,1 )

② priority[0][1] = 1 이 sort_priority[0] =9와 다름

=> priorirty[0][1]의 값을 popleft()하고 뒤에 append함

priority:  (몇번째 숫자인지, 중요도)
( 2,9 )	( 3,1 )	( 4,1 )	( 5,1 )	( 0,1 )	( 1,1 )

③ priority[0][1] = 9 이 sort_priority[0] =9와 같음

=> priority[0][0] = 2와 m(찾고자 하는 정수 )=0이 같은 지 확인하기 -> X

-> (2,9) popleft() : Queue에 2번째 놓여 있는 정수가 첫번째로 나옴, sort_priority[0] popleft() 하기

priority:  (몇번째 숫자인지, 중요도)
( 3,1 )	( 4,1 )	( 5,1 )	( 0,1 )	( 1,1 )

sort_priorty: 중요도를 정렬시킨 리스트
1	1	1	1	1

④ priority[0][1] = 1이 sort_priority[0] = 1와 같음

=> priority[0][0] = 3과 m(찾고자 하는 정수)=0이 같은 지 확인하기 -> X

-> (3,1) popleft(): Queue에 3번째 놓여 있는 정수가 두번째로 나옴, sort_priorty[0] popleft() 하기

priority:  (몇번째 숫자인지, 중요도)
( 4,1 )	( 5,1 )	( 0,1 )	( 1,1 )

sort_priorty: 중요도를 정렬시킨 리스트
1	1	1	1

⑤ priority[0][1] = 1이 sort_priority[0] = 1와 같음

=> priority[0][0] = 4와 m(찾고자 하는 정수)=0이 같은 지 확인하기 -> X

-> (4,1) popleft(): Queue에 4번째 놓여 있는 정수가 세번째로 나옴, sort_priorty[0] popleft() 하기

priority:  (몇번째 숫자인지, 중요도)
( 5,1 )	( 0,1 )	( 1,1 )

sort_priorty: 중요도를 정렬시킨 리스트
1	1	1

⑥ priority[0][1] = 1이 sort_priority[0] = 1와 같음

=> priority[0][0] = 5와  m(찾고자 하는 정수)=0이 같은 지 확인하기 -> X

-> (5,1) popleft(): Queue에 5번째 놓여 있는 정수가 네번째로 나옴, sort_priorty[0] popleft() 하기

priority:  (몇번째 숫자인지, 중요도)
( 0,1 )	( 1,1 )

sort_priorty: 중요도를 정렬시킨 리스트
1	1

⑦ priority[0][1] = 1이 sort_priority[0] = 1와 같음

=> priority[0][0] = 0와  m(찾고자 하는 정수)=0이 같은 지 확인하기 ->O

-> (0,1) 은 Queue에 0번째 놓여 있는 정수가 다섯번째로 나옴

따라서 5번째로 인쇄된다라고 5를 출력한다.

 

💻Python(파이썬)

import sys
from collections import deque
#테스트 케이스 수
num = int(sys.stdin.readline())
for i in range(num):
    #문서의 개수(n), 몇번째 놓여져 있는지를 나타내는 정수(m)
    n,m = map(int,sys.stdin.readline().split())
    #n개의 문서의 중요도
    p = list(map(int,sys.stdin.readline().split()))
    priority = deque()
    for index in range(n):
        #(몇번째 숫자인지, 중요도)
        priority.append((index,p[index]))
    #중요도를 정렬시킨 리스트
    sort_priority= deque(sorted((j for i,j in priority),reverse=True))
    #몇번째로 출력될 지
    i=1
    while priority:
        #중요도가 정렬시킨 중요도와 같은 경우
        if priority[0][1] == sort_priority[0]:
            #내가 찾고자하는 숫자인지 확인하기
            if priority[0][0] == m:
                print(i)
                break
            i+=1
            priority.popleft()
            sort_priority.popleft()
        #같지 않은 경우
        else:
            #제일 앞에 있는 숫자를 pop해서 뒤로 append
            priority.append((priority.popleft()))