1966번: 프린터 큐(파이썬, 풀이, 정답코드)

1966번: 프린터 큐 (acmicpc.net)

1966번: 프린터 큐

프린터에 들어간 종이들에 가중치가 있고, 가중치가 높은 순으로 종이를 출력해야 한다니, 이거 완전 우선순위 큐 아니냐?! 하신 분들은 나처럼 이 문제를 북마크하면 되시겠다. 이 문제에 주의깊게 봐야할 지점은 바로 중요도가 같은 종이들의 출력 순서이다. 기본적으로는 배열의 왼쪽부터 출력을 걸도록 되어 있어 그 부분에 대한 처리가 필요하다. 예제에서 세번째 케이스가 좋은 예시가 된다. 한 종이만 중요도가 9이고, 나머지는 전부 같은 상태에서 첫번째로 들어온 종이가 출력될 순서는 5번째이다.

구현

사실 문제의 입력 제한이 100으로 엄청 작은데 시간은 2초나 주는 매우 혜자스러운 문제라 시간 복잡도를 과하게 계산할 필요는 없다. 시간이나 공간에서의 제한이 딱히 없다면 문제에서 나오는 매커니즘을 그대로 '구현'하는 것이 가장 쉽게 떠올릴 수 있는 풀이 방법이 될 것이다.

정답 코드

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):
	n, m = map(int,input().split())
	inlst = map(int, input().split())
	lst = deque((j,i) for i, j in enumerate(inlst))
	count = 0
	while True:
		if max(lst)[0] == lst[0][0]:
			count += 1
			tmp = lst.popleft()
			if tmp[1] == m:
				print(count)
				break
		else: lst.rotate(-1)

그래서 말 그대로 구현한 모습. 맨 앞에 있는 원소를 뒤로 보내는 작업은 deque의 rotate를 통해 쉽게 할 수 있다. 또한 deque는 연결리스트의 방식으로 자료구조가 이뤄져 있어 pop을 하는 작업이 일반 리스트에 비해서 빠른 것으로 알고 있어 거리낌없이 deque를 활용했다. 내가 대충 알고 있는 바로는 deque가 모든 면에서 리스트에 비해 우월한지라, 배열을 순회하는 것 이외에 추가적인 작업을 하고싶다면 웬만해서는 deque를 쓰는 게 안전하다.

일단 lst에 각 종이의 중요도와 순서를 묶어서 담는다. 그 이후 while문을 돌면서 문제에 나와있는 과정을 그대로 밟아주면 된다.