[백준] 최대,최소 힙 (Python)

문제 출처 :

www.acmicpc.net/problem/1927

1927번: 최소 힙

www.acmicpc.net/problem/11279

11279번: 최대 힙

 

문제 풀이 :

• 파이썬에서는 heap 모듈을 기본 라이브러리로 제공해준다.( 이건 기본 코딩테스트에서는 쓸 수 있다. 빡고수님들은 직접 구현해서 쓰시겟지만 나는...)
• 기본 모듈에선 최소힙만을 제공해주는데 그 이유는 사실 최대힙은 따로 구현하지 않아도 최소 힙에 값을 -붙여서 반전으로 넣어줌으로써 간단히 사용할 수 있기 때문이다.
• 사용법은 다음 블로그를 참고햇다.

최소힙

import heapq
import sys
n= int(sys.stdin.readline())
heap =[]

for i in range(n):
    temp = int(sys.stdin.readline())
    if temp ==0:
        if(len(heap)==0):
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap,temp)

 

최대힙

import heapq
import sys
n= int(sys.stdin.readline())
heap =[]

for i in range(n):
    temp = int(sys.stdin.readline())
    if temp ==0:
        if(len(heap)==0):
            print(0)
        else:
            a= heapq.heappop(heap)
            print(-a)
    else:
        heapq.heappush(heap,-temp)