백준(S2) 11279번: 최대 힙(파이썬, Python3)및 heapq 설명

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

11279번: 최대 힙

나는 자료구조를 C언어로 배워서 최대 힙을 구현할 때 C언어는 구현하기 위해 10~20줄 정도 필요 한 것으로 알고 있는데 파이썬은  heapq를 import 하면 끝나는 것을 알고 매우 놀랐다... (정말 좋은 언어다 파이썬)

 

문제를 풀기 위해 heapq와 heapq의 함수들을 간단하게 설명하자면

우선 heapq는 최소힙으로 숫자들을 정렬한다.

부모노드가 자식노드보다 작은 힙을 최소 힙이라 한다. 오름차순과 비슷하지만 다른 면이 있다.

heapq.heappush(heap,(number))

이렇게 heappush라는 함수를 사용하면  heap이라는 리스트에 number이라는 데이터를 최소히프에 준수해서 추가한다. 항상 값을 추가하면 값을 추출할줄도 알아야 한다.

num = (heapq.heappop(heap))

heappop이라는 함수를 사용하면 heap에 있는 가장 작은 인자를 추출한다.(가장 위에 있는 인자를 추출한다)

그러나 이때 단점이 있다. heappop 함수는 heap에 인자가 없으면 에러를 발생시킨다.

그러므로 try except를 사용해서 함수를 사용하면 편리하다.

 

 

우선 첫째 줄에 연산의 개수가 주어지고 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수가 주어진다를 인지해야 한다. 그 후, 0이 입력되면 최대값을 출력하고 0이 아닐 때는 값을 넣는 규칙을 알아야 한다.

 

지금 문제 이름도 최대 히프고 우리가 필요한 데이터는 최대값인데 최소 히프로는 구현하기가 어렵다.

이럴 때 쉽게 사용할 수 있는 방법이 있다.

 

heapq.heappush(heap,(-num))

이렇게 값을 음수값으로 저장 한 뒤 

num = (-1 * heapq.heappop(heap))

추출할 때 -1을 곱해준 값으로 추출을 하면 최대 히프를 쉽게 구현할 수 있다.

 

정답 코드

import heapq
import sys
heap = []
number = int(input())
for i in range(number):
    mis_num = int(sys.stdin.readline())
    if mis_num != 0:
        heapq.heappush(heap,(-num))
    else:
        try:
            num = (-1 * heapq.heappop(heap))
            print(num)
        except:
            print("0")