[Heap] 백준 Sliver 2 1927 최소힙

문제

 

https://www.acmicpc.net/problem/1927

---

설계 ✨

힙에 대해서 공부 후에 문제를 풀었다. 

Heap은 최대값, 최소값을 찾는 연산을 빠르게 하기위해 고안된 완전이진트리를 기본으로 한다. 

이 문제는 시간초과 조건이 포함되어있고, 배열에서 가장 작은 값을 찾으라고 하였기 때문에 힙을 쓰는 것이 좋다. 

 

• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

파이썬에서는 힙 알고리즘을 heapq라는 내장모듈을 import하면 쓸 수 있다. 

다음은 heapq의 주요 함수 기능이다.

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함

 

heapq는 기본적으로 최소힙으로 구현한다.

최대힙으로 구현하고 싶다면, 부호를 바꿔서 최소힙에 넣어준 뒤에서 최솟값부터 pop 해줄때 다시 부호를 바꿔주면 된다.

관련해서 밑의 블로그를 참고했다.

import heapq

heap = []
values = [1,5,3,2,4]

# 아래 for문을 실행시키고 나면 heap은 [-5,-4,-3,-1,-2]가 된다.
for value in values:
	heapq.heappush(heap, -value)

# 아래 for문을 실행시키면 5,4,3,2,1이 출력된다. 즉, 큰 숫자부터 출력이 된다.
for i in range(5):
	print(-heapq.heappop(heap))

 

[Python] heapq를 이용한 최소 힙, 최대 힙

 

 

---

코드  📁

import heapq
# heapq는 기본적으로 최소힙으로 구현
# 최대힙으로 구현하고 싶으면?
# -> 부호를 바꿔서 최소 힙에 넣어준 뒤에 최솟값부터 pop을 해줄 때 다시 부호를 바꿔주기
# heqpq의 heappush를 통해 값을 삽입하면 해당 값들을 숫자가 가장 작은 순서대로 트리 구조로 값 저장

from sys import stdin  # 시간초과 입력 해결
n = int(stdin.readline())
heap = []
smallest = []
for i in range(n):
    x= int(stdin.readline())
    if x == 0:
        if heap:
            # 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거
            # heappop 연산을 통해 우선순위 큐의 가장 우선순위가 높은 값(최소값)을 제거할 수 있다.
            smallest.append(heapq.heappop(heap))
        else:
            smallest.append(0)

    else:
        # 배열에 x라는 값을 추가
        heapq.heappush(heap, x)

for i in smallest:
    print(i)