[파이썬] 프로그래머스 명예의 전당 (1) 풀이

문제 확인

프로그래머스

나의 풀이

• $k$개의 점수만 기록하려면 점수를 정렬해서 관리하는 것이 필요하다.
• $k$일 이후에는 가장 작은 값 1개만 제거하면 되기 때문에 우선 순위 큐를 사용해 시간 복잡도를 줄였다.
• 우선 순위큐의 push, pop의 시간 복잡도는 $O(\log N)$이다.

import heapq

def solution(k, score):
    answer = []
    # 최하 점수만 확인하면 되기 때문에 heapq 사용
    heap = []
    for i in score:
        heapq.heappush(heap, i)
        # 개수 초과 시 제거
        if len(heap) > k:
            heapq.heappop(heap)
        answer.append(heap[0])
    return answer