[BOJ-1966] 프린터 큐

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

1966번: 프린터 큐

---

[풀이]

큐를 이용한 문제이다. 굳이 큐를 넣지 않아도 연결리스트로 풀 수 있는 문제이기도하다.

나는 큐(deque)을 이용하기 보다는 그냥 리스트로 풀었다.

 

일단 나는 중요도번호(1~9)와 문서 위치(0~N)을 리스트원소로했다.

즉 이렇게 말이다 "(문서위치, 중요도)"

 

그리고 리스트의 맨앞원소값을 pop(0)한다. 

pop(0)는 맨왼쪽의 원소를 pop한다 (deque의 popleft()와 같은 기능이나 시간 복잡도가 O(N)이다.)

 

 

그리고 pop한 값을 now라고 하면

큐의 맨왼쪽원소가 now보다 큰원소가 존재한다면 now를 현재큐의 맨 오른쪽에 append시킨다. 

여기서 큐는 연결 리스트 큐(que)이다.

 

반면, 큐의 맨왼쪽원소가 now보다 모두 작다면 now를 printer이라는 임시저장 리스트에 넣는다.

 

예를 들어서 설명해보겠다.

N은 문서의 개수

priority 문서의 중요도를 담은 문서 리스트

M은 내가 몇번째로 뽑혔는지 알고 싶은 문서의 위치

(즉, M=0이면 nums의 인덱스가 0(priority[0])인 문서를 의미한다)

 

(1) N=1, M=0, priority=[5] 

문서의 개수가 한개이면 맨왼쪽의 문서 1개만 프린트하면 되므로 1이나온다.

 

(2) N=4, M=2, priority=[1,2,3,4]

 

 

 

 

 

---

[코드]

import sys
input=sys.stdin.readline

def find_bigger(now, priority):
    for e in priority:
        if e[1]>now:
            return True
    return False

def solution(N,M,nums):
        #N: 문서개수
        #M: 몇번째로 인쇄됐는지 궁금한 문서 번호
        if N==1: #문서개수가 1개인경우
            return 1
            
        else:
            #중요도 idx는 1~9이다.
            priority=[(idx, val) for idx, val in enumerate(nums)]        
            printer=[]
            while len(que)>0:
                now=priority.pop(0)
                #now[1]보다 큰 값이 que에 존재한다면-> 맨앞값을 큐에넣는다.
                if find_bigger(now[1], priority):
                    priority.append(now)
                else:#now[1]보다 큰값이 존재하지 않으면 -> 맨앞값을 프린터에 넣는다.
                    printer.append(now)
     
            for idx,p in enumerate(printer):
                if p[0]==M:
                    return idx+1
                    

def main():
    T=int(input()) #테스트케이스 개수
    for _ in range(T):
        N, M=map(int, input().strip().split())
        nums=[*map(int, input().strip().split())]
        print(solution(N,M,nums))

if __name__=='__main__':
    main()
                ​