프린터 큐[백준 1966]

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

1966번: 프린터 큐

 

우선순위가 껴있어서 우선순위 큐를 사용해야지 했다가 우여곡절을 겪은 문제다.

당연히 우선순위큐를 이용해서 풀수도 있겠지만

작성하고 있던 코드는 계속 산으로 가서 방법을 수정했다.

처음보면 테스트 케이스에서 3번 예제가 이해 안될법 한데 문제 잘 읽으면 이해 될거에요

 

아래는 정답 코드다.

tc = int(input())

for _ in range(tc) : 
  n, m = list(map(int, input().split()))
  array = list(map(int, input().split()))
  index = list(range(len(array)))
  index[m] = 'target'
  order = 0
  
  while True :
    if array[0] == max(array) :
      order += 1
      if index[0] == 'target' :
        print(order)
        break
      else :
        array.pop(0)
        index.pop(0)

    else :
      index.append(index.pop(0))
      array.append(array.pop(0))

 

유의할 점

1. 순서를 올릴때는 우선순위가 제일 높은걸 처리할때만 올려주어야 한다.
2. 문제에서 우선순위가 아닌 프린터의 큐는 큐의 맨 뒤로 보내주어야 한다. 이때 deque를 쓰면 append, popleft를 사용하면 된다.
3. 2번에서 append, popleft로 접근해야 한다. appendleft로 해주었어서 삽질했다.
4. 우선순위 큐로 설정을 해버리면 값이 입력될 때 정렬이 되어버리기 때문에 큐에서 맨 뒤로 보내는 구문을 직접 작성했다.
5. 우선순위 큐로 접근 했을때 우선순위 value가 낮은 값이 맨 앞으로 가버려서 매번 -1을 곱해서 설정했었는데 방법을 찾아봐야 겠다.

from queue import PriorityQueue

pq = PriorityQueue()
pq.put(-1)
pq.put(-2)
pq.put(-3)

pq.get(0) # -3
pq.get(0) # -2
pq.get(0) # -1

pq.put(-1)
pq.put(-2)
pq.put(-3)

pq.get(0) * -1 # 3
pq.get(0) * -1 # 2
pq.get(0) * -1 # 1