[Algorithm] 백준 1966 - 프린터 큐 in Python(파이썬)

💡 백준 1966:

큐 기본 구조 및 우선순위 큐 방식 활용

🌱 코드 in Python

알고리즘: Queue

import sys, heapq

t = int(sys.stdin.readline())
for i in range(t):
	n, m = map(int, sys.stdin.readline().split())
	idx_list = list(enumerate((map(int, sys.stdin.readline().split())))) # 최초 index 정보 저장을 위해 튜플 형태로 입력
	hq = [] # 문서의 중요도를 우선순위에 따라 배치하기 위해 heqpq 배열로 정보 재저장
	for j in range(n):
		heapq.heappush(hq, -idx_list[j][1]) # max_heap 구조를 위해 - 연산 후 저장
	cnt = 0
	while cnt <= n:
		if idx_list[0][1] == -hq[0] and idx_list[0][0] == m: # 현재 배열 첫번째 문서의 중요도와 우선순위 배열의 첫번째 중요도(가장 우선순위가 높은 것)와 같고, 그 문서의 인덱스가 처음 찾으려는 인덱스와 같을 경우 
			cnt += 1 # 카운트 증가 후 while문 중단
			break
		elif idx_list[0][1] == -hq[0]: # 현재 배열 첫번재 문서의 중요도와 우선순위 배열의 첫번째 중요도(가장 우선순위가 높은 것)와 같을 경우
			del idx_list[0] # 문서 삭제 == 출력
			heapq.heappop(hq) # 중요도 삭제 == 출력
			cnt += 1 # 출력 카운트 증가
		else: # 우선순위가 낮은 문서가 가장 첫번째에 잇을 경우
			idx_list.append(idx_list[0]) # 첫번째 문서를 뒤로 돌림
			del idx_list[0]
	print(cnt)

이번 문제는 큐 자료구조를 다루면서 우선순위를 부여한 문제였다

처음 이 문제를 접하고 (priority, idx) 형태의 튜플로 저장하고 heapq.heapify() 함수를 통해서
1) 우선순위 순 -> 2) 같은 우선순위일 경우 idx 순으로 정렬시키는 꼼수를 부려보려 하였다

그러나 그렇게 녹록할리 없지!
heapify()는 튜플의 경우 앞의 원소만 가지고 min_heap 구조를 만들어주었다

import sys, heapq

q = [(-7, 1), (-1, 2), (-1, 3), (-1, 4), (-4, 5)]
heapq.heapify(q)
print(q)

위와 같이 배열을 만들었을 때 나의 희망사항은
(-7, 1), (-4, 5), (-1, 2), (-1, 3), (-1, 4) 였지만

실제 결과는

깜찍하게도 이렇게 나온다 ㅎ__ㅎ
그래서,,, heapify()는 나는 내가 원하는 결과를 만들지 못했다

결론적으로는 우선수위를 max_heap 구조로 배열을 따로 만들어놓고 프린터 큐와 우선순위 큐를 비교하여
현재 가장 높은 우선순위를 가진 문서가 프린터 큐의 0번째에 올 때까지 큐를 회전시키는 방법을 택하게 되었다

프린터 큐의 첫번째 문서가 가장 우선순위가 높은 문서일 경우
우선순위가 같은 문서들이 존재할 수 있으므로 추가적으로 내가 추적하려는 문서가 맞는지를 확인하기 위해 idx를 같이 비교해주었다

다른 코드를 조금 찾아보니 max(num) 함수를 활용하여 그때그때 뽑아야 하는 출력물의 우선순위를 판단하는 코드도 많이 보였다 나는 그걸 max_heap 큐로 한 것 일뿐 속도 차이는 크게 나지 않는 것 같았다 뭔가 코드가 조금 지저분해보여서 다듬고 싶었는데 일단은 이게 최선인 걸루..

---

🧠 기억하자

1. heapify() 튜플에선 앞 원소만 가지고 min_heap을 만들어 준다..

2. 조금이라도 더 단순하게 생각할 수 있도록 해보자

백준 10845 바로가기