[Python] 백준 #11729 - 최대 힙

문제

---

11279번: 최대 힙

코드

---

My answer

import sys
import heapq
input=sys.stdin.readline

n=int(input())
heap = []

for i in range(n):
    tmp=int(input())
    if(tmp!=0):
        heapq.heappush(heap, (-tmp, tmp))
    else:
        if(heap==[]):
            print(0)
        else:
            result=heapq.heappop(heap)
            print(result[1])

Another answer

import heapq,sys
input=sys.stdin.readline
h=[]
for _ in range(int(input())):
	n=-int(input())
	if n:heapq.heappush(h,n)
	else:print(-heapq.heappop(h) if h else 0)

풀이

---

맨처음에는 그냥 단순 큐처럼 구현해서 append를 한 뒤에 sort를 사용했는데, 시간초과가 떠서 다음으로는 스택2개를 만들어서 정렬을 해서 풀었는데도 시간초과가 떴다. 힙이라는 자료구조를 안접해봤어서 문제에 대놓고 힙이라고 써져있는데 쓸데없는걸 했었다. 힙알고리즘을 이해한뒤에 코드로 구현하려했는데, 재귀를 써야할지 반복문을 써야할지 모르겠어서 찾아보니 파이썬에는 힙 모듈이 따로 있었다..역시 파이썬.. 우선 import heapq를 한뒤에 사용하는데, 파이썬이 기본적으로 제공하는 힙은 최소힙이다. 최소힙과 최대힙의 힙 개념은 알고리즘 카테고리에 작성하겠다. 그래서 문제는 최대 힙문제이므로 나는 튜플 형식으로 어떤수를 입력받으면 음수형태와, 입력값을 튜플형태로 넣은뒤에 힙함수에 의해 최소힙으로 구현된 힙에서 마지막 출력때 튜플(음수,양수)중 양수만을 출력했다. 아래 방법도 똑같은데 애초에 그냥 입력값을 음수로 넣고 출력할 때 다시 양수로 바꿔서 출력했다.