[Programmers] L1. 명예의 전당 (최소 힙/Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

1️⃣ 명예의 전당 유지

• 명예의 전당은 k 개의 점수를 유지하며, kkk개를 초과하면 가장 낮은 점수를 제거
• 우선순위 큐(최소 힙)를 활용하면 효율적으로 관리 가능

2️⃣ 최하위 점수 추출

• 매번 명예의 전당에서 최하위 점수를 확인하여 기록

3️⃣ 점수 처리

• 점수를 하나씩 추가하며 명예의 전당을 업데이트
• 명예의 전당이 가득 차면 최저 점수와 비교 후 대체

Solution

최소 힙 구현

import heapq

def solution(k, score):
    hall_of_fame = []  # 명예의 전당 (최소 힙)
    result = []

    for s in score:
        heapq.heappush(hall_of_fame, s)  # 점수 추가
        if len(hall_of_fame) > k:  # 크기 초과 시 최소값 제거
            heapq.heappop(hall_of_fame)
        result.append(hall_of_fame[0])  # 현재 명예의 전당의 최하위 점수 기록

    return result

• heapq 사용
  • 최소 힙으로 명예의 전당 점수를 관리
  • 점수 추가 및 삭제 시 O(logk)로 처리 가능
• result에 최하위 점수 추가
  • 매일 명예의 전당에서 가장 낮은 점수를 결과 리스트에 추가
• 시간 복잡도
  • 점수 배열의 길이가 n일 때, 최대 O(nlog⁡k)

 

단순 구현

def solution(k, score):
    answer = []
    top = []

    for s in score:
        top.append(s)
        if len(top) > k:  # 명예의 전당 크기를 초과하면 최소값 제거
            top.remove(min(top))
        answer.append(min(top))  # 현재 명예의 전당의 최하위 점수 기록

    return answer

 

---