⚠️ 문제
https://school.programmers.co.kr/learn/courses/30/lessons/138477
🔐 풀이
heapq를 통해 min heap으로 해결할 수 있습니다.
min heap으로 구현함으로써 honor[0]을 통해 매번 정렬하지 않고도 명예의 전당 최하위 점수를 알 수 있습니다.
k일까지 모두 heapq.heappush를 통해 명예의 전당에 넣고,
이후에는 명예의 전당 최하위 점수가 새로운 점수보다 낮다면 기존의 최하위 점수를 heapq.heappop(honor)로 힙에서 제거한 후 새로운 점수를 힙에 넣어줍니다. 이렇게 되면 매일 honor[0]이 그 날의 최하위 점수가 됩니다.
🧑🏻💻 코드
import heapq
def solution(k, score):
answer = []
honor = []
for today_score in score:
# k일까지 모두 명예의 전당
if len(honor) < k:
heapq.heappush(honor, today_score)
else:
# k일 지났고, 명예의 전당에서 가장 낮은 점수가 새로운 점수보다 낮을 때
if honor[0] < today_score:
# 가장 낮은 점수 명예의 전당에서 제거
heapq.heappop(honor)
heapq.heappush(honor, today_score)
# 그 날의 최하위 점수 저장
answer.append(honor[0])
return answer