[Programmers][Python] Lv.1 명예의 전당(1)

Overview

• 체감 난이도: ★★★☆☆ (힙을 사용하는 방법을 몰랐음)
• 문제 레벨: Lv.1
• 문제 유형: 힙, 우선순위큐, 구현
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

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

프로그래머스

 

 

[코드]

import heapq


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

    for s in score:
        heapq.heappush(min_heap, s)
        if len(min_heap) > k:
            heapq.heappop(min_heap)

        answer.append(min_heap[0])

    return answer

 

[배운 점]

힙(Heap)

: 이진 트리 형태의 자료 구조로, 최대 힙, 최소 힙이 있다. 

- 최소 힙: 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 구조(최솟값을 빠르게 찾을 수 있다.)

 

* 기본적으로 파이썬으로 힙을 구현할 때, 최소 힙으로 설정되어 있다. 

 

힙큐 모듈(heapq)

: 파이썬 표준 라이브러리 중 하나, 힙 자료 구조를 구현한 모듈

- heapq.heappush(heap, item) : 힙에 아이템을 추가한다. 

- heapq.heappop(heap) : 힙에서 최솟값을 제거하고 반환한다. 

 

https://docs.python.org/ko/3/library/heapq.html

heapq — Heap queue algorithm

 

 

우선순위 큐(Priority Queue)

: 힙은 우선순위 큐를 구현하는 데 사용된다. 우선순위 큐는 각 요소가 우선순위를 가지며, 가장 높은 우선순위를 가진 요소가 먼저 나가는 큐이다.