[백준-Python] 프린터 큐 : 1966번

🥈 Silver3

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

 

 

✅ 정답풀이

# 인쇄=맨앞요소 제거시, 
# list(stack)는 pop(0)=O(n)
# Queue는 popleft()=O(1)  -> Queue 사용

# 첫번째 요소가 queue에서 max값이여야 출력이 가능

import sys
from collections import deque
input=sys.stdin.readline
n=int(input())
find=False


for _ in range(n):
    q=deque() #queue 생성 

    n,target=map(int,input().split())
    priority=list(map(int,input().split()))
    
    for idx,p in enumerate(priority):
        q.append((idx,p)) #(index:우선순위)
    
    result=0
    
    while True:
        # 첫번째 요소가 현재 큐에서 가장 큰 우선순위인지 확인
        max_priority=max(q,key=lambda x:x[1])[1]
        first=q.popleft()
  

        if first[1]==max_priority:
            result+=1
            #target 확인
            if target==first[0]:
              print(result)
              break
        else:
            #뒤로가기
            q.append(first)

 

이 문제는 프로그래머스의 프로세스와 굉장히 유사한 문제이다. 

예전에 그 문제를 풀때 어려워했던걸로 기억하는데.. 이번에도 오래걸렸다 😣

그때는  dictionary를 잘 다루지 못해서 배열을 사용했고, js특성상 queue가 아닌 형태로 풀었다.

이번에는 처음엔 딕셔너리로 풀어볼까 했지만 값을 뽑아서 사용하기에 코드가 너무 복잡해서 튜플로 변경하였다.

이래서 튜플이 있나보다.. 이거 풀어본뒤론 튜플을 적극 활용중이다 👍🏻

 

찾고자하는 index가 큐에서 나올때까지 순회를 해야하므로 while문을 사용해주고, 

현재 큐에서 가장 첫번째요소를 기준으로 큰 수가 있는지 확인하기 위해 처음엔 for문을 사용해보려고 했지만, 유동적이기 때문에 코드 짜기도 어렵고 복잡했다. 다시 한번 생각해보니, 출력할 기회가 주어지는 첫번째요소가 현재 큐를 기준으로 가장 큰 우선순위를 가질때까지 출력을 할 수가 없다. 

 

👉🏻 max를 사용해 가장 큰 우선순위가 현재 첫번째요소와 일치한다면, 출력이 가능하다. 

👉🏻 target이 몇번째로 출력되는지가 문제이기 때문에, 카운트를 해주다가 target을 만나게 되면 출력해주고, 종료하면된다!