[LV.3] 연습문제 > 명예의 전당 (1) ⭐️

# heapq 활용

문제

https://school.programmers.co.kr/learn/courses/30/lessons/138477

프로그래머스

---

문제 설명

• TV 프로그램 "명예의 전당"에서는 매일 가수의 점수가 발표되고, 시청자들의 문자 투표로 가수에게 점수 부여
• 매일 발표되는 명예의 전당에서, 가수의 점수가 상위 k번째 이내일 경우 해당 가수의 점수가 명예의 전당에 추가
• 초기에는 k일간 모든 점수가 명예의 전당에 올라가며, 그 이후부터는 새로운 가수의 점수가 기존 명예의 전당의 k번째 점수보다 높으면 추가되고, 기존 점수는 내려옴
• 이 문제는 매일 발표되는 명예의 전당의 최하위 점수를 구하는 문제
• 제한사항
  3 ≤ k ≤ 100
  7 ≤ score의 길이 ≤ 1,000
  0 ≤ score[i] ≤ 2,000

---

정답 코드

import heapq

def solution(k, score):
    honor = []   # 명예의 전당 (최소 힙)
    answer = []  # 매일 발표된 최하위 점수

    for s in score:
        heapq.heappush(honor, s)   # 점수를 명예의 전당에 추가
        if len(honor) > k:         # 명예의 전당 크기가 k를 초과하면
            heapq.heappop(honor)   # 가장 작은 점수를 제거 (최소 힙에서)
        answer.append(honor[0])    # 현재 명예의 전당에서 최하위 점수 기록

    return answer

• honor[0]: honor는 최소 힙이기 때문에, 가장 작은 값은 항상 honor[0]에 있음 → 이를 매일의 최하위 점수로 기록

---

heapq 이란?

• 개념
  • heapq는 파이썬 내장 힙(Heap) 자료구조 모듈
  • 기본은 최소 힙(min heap) 구조
    → 항상 가장 작은 값이 인덱스 0에 위치함
  • 최대 힙은 지원하지 않음, 대신 음수로 바꿔 넣어 흉내낼 수 있음
• 특징
  • 우선순위 큐(Priority Queue) 구현에 사용
  • 정렬 없이도 최솟값/최댓값을 빠르게 꺼냄
  • 삽입/삭제 시간 복잡도: O(log n)
• 기본 사용법 예제

import heapq  # heapq 모듈 불러오기 (파이썬 표준 힙 라이브러리)

nums = []  # 빈 힙(리스트) 생성

heapq.heappush(nums, 5)  # 5를 힙에 추가 → [5]
heapq.heappush(nums, 2)  # 2를 추가 → [2, 5] (자동 정렬됨: 가장 작은 값이 앞으로)
heapq.heappush(nums, 8)  # 8 추가 → [2, 5, 8] (힙 구조 유지)

print(heapq.heappop(nums))  # 2 출력: 가장 작은 값 (맨 앞의 값)을 꺼냄 → 남은 힙: [5, 8]
print(heapq.heappop(nums))  # 5 출력: 그다음 작은 값 → 남은 힙: [8]

• 최대 힙 만들기 (Tip)

import heapq  # 힙 모듈 불러오기

nums = []  # 빈 리스트(힙) 생성

heapq.heappush(nums, -5)  # -5를 추가 → 실제 값 5를 최대 힙처럼 다루기 위해 음수로 저장
heapq.heappush(nums, -2)  # -2 추가 → 실제 값 2
heapq.heappush(nums, -8)  # -8 추가 → 실제 값 8

print(-heapq.heappop(nums))  # 가장 작은 음수 값인 -8 꺼내고 다시 음수 붙여서 8 출력 → 실제로는 가장 큰 값 꺼낸 셈

---

첫 번째 시도 (실패)

def solution(k, score):
    medi = []
    answer = []
    
    for i in range(len(score)):
        medi.append(score[i])
        medi.sort(reverse=True)
        
        if len(medi) < k+1:
            answer.append(medi[-1])
        else:
            answer.remove(medi[-1])
            answer.append(medi[-1])
            
    return answer

---

문제점

• answer.remove() → answer는 결과 리스트인데 여기서 값 제거는 오작동
• medi 크기 제한 안 함 → 계속 커져서 비효율
• 매번 정렬해서 시간 많이 소요→ 매번 반복해야되는거 아닌가??..

---

첫 번째 시도 (성공. 개선필요)

def solution(k, score):
    medi = []
    answer = []
    
    for i in range(len(score)):
        medi.append(score[i])
        medi.sort(reverse=True)
        
        if len(medi) < k+1:
            answer.append(medi[-1])
        else:
            medi.remove(medi[-1])
            answer.append(medi[-1])
            
    return answer

---

개선점

• medi.sort(reverse=True) : 불필요한 정렬 계속 발생
• remove()는 O(n) 시간 소모
• pop() 활용하면 조금 낫지만, heapq가 더 적합