소스코드
큐만 사용
import sys
from collections import deque
T = int(input().strip())
for _ in range(T):
N,M = map(int, input().strip())
data = list(map(int, input().strip().split()))
printer_count = 0 # 현재까지 프린트 횟수
printer_queue = deque([(idx,priority] for idx,priority in enumerate(data))
while printer_queue:
idx, priority = printer_queue.popleft()
if priority == max([p for _, p in printer_queue]):
printer_count += 1
# 만약 찾고자 했던 M 인덱스에 해당하는 문서라면
if idx == M:
break
else:
printer_queue.append((idx, priority))
print(printer_count)
Python
복사
최대힙 + 큐 사용
import sys
import heapq
from collections import deque
T = int(input().strip())
for _ in range(T):
N,M = map(int, input().strip().split())
data = list(map(int, input().strip().split())) # 문서들의 중요도
printer_count = 0 # 현재까지 프린트 횟수
printer_queue = deque([(idx,priority) for idx,priority in enumerate(data)])
max_heap = [-p for p in data]
heapq.heapify(max_heap)
while printer_queue:
idx, priority = printer_queue.popleft()
if priority == -(max_heap[0]):
printer_count += 1
heapq.heappop(max_heap)
if idx == M:
break
else:
printer_queue.append((idx, priority))
print(printer_count)
Python
복사
풀이
•
M번째 인덱스의 위치를 마지막에 비교하고 같으면 출력해야하므로 인덱스도 프린터 큐에 같이 보관해야합니다. 중요도 또한 원소에 저장해둬야 원소끼리 비교하거나 할 수 있으므로 같이 보관해야한다고 판단했습니다.
•
큐에서 하나씩 왼쪽에서 꺼내서 중요도가 가장 높은지를 확인합니다
◦
큐만 사용할 경우 → 선형탐색
◦
최대힙도 사용할 경우 → 힙의 최대값과 비교
•
만약 중요도가 가장 높다면
◦
프린트 횟수를 증가하고
◦
찾고자했던 인덱스의 문서인지 확인하고, 맞으면 반복을 중지합니다.
•
만약 중요도가 가장 높은게 아니라면
◦
큐에서 꺼냈던 원소를 다시 큐의 오른쪽 끝에 append합니다.
복기
•
힙을 생각을 했는데, 어느 시점에 써야하나 빠르게 판단하지 못해서 그냥 사용을 안 했습니다. 힙의 개념을 아는 것과 실제 자유롭게 사용할 줄 아는 것의 괴리감을 느껴서 여러 번 복습을 하며 힙의 사용사례들을 많이 눈에 익혀둬야겠다고 느꼈습니다.
◦
해당 문제에서는 문서가 많아야 100개이므로 선형탐색을 해도 문제가 안됩니다