알고리즘/백준 문제풀이
[백준] 1927번 : 최소힙 (python 파이썬)
매일_공부
2022. 3. 10. 14:09
반응형
https://www.acmicpc.net/problem/1927
문제정리 : N번 수행하는동안 자연수 x가 주어지면 배열에 추가, 0인 x가 주어지면 최솟값 출력 및 제거(pop)
# heapq 및 sys import
import heapq
import sys
h = [] #배열 생성
n = int(sys.stdin.readline()) #n값 받기
for i in range(n): #n번 수행
x = int(sys.stdin.readline()) #x값 받기
if x == 0: #x가 0일 때
if len(h) == 0: #배열에 아무것도 없을 경우
print(0)
else:
result = heapq.heappop(h) #최솟값 출력 및 제거
print(result)
else: #x가 자연수일 경우
heapq.heappush(h, x) #배열에 값 넣기
파이썬 heapq 모듈을 통한 heapq 알고리즘을 이용한다.
heapq.heappush(heap, item) : item 을 heap에 추가 [O(log n)]
heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출된다. [O(1)]
heapq.heapify(x) : 리스트 x를 heap으로 변환 [in linear time, O(N)]
반응형