[백준] 11279번 최대 힙 ( 파이썬 )

문제

 

11279번: 최대 힙

 

풀이 (Python)

import heapq
import sys
N=int(input())
num=0


Heapq=[]
for i in range(N):
    num=int(sys.stdin.readline())
    if num==0:
        if len(Heapq)==0:print(0)
        else:
            print(-Heapq[0])
            heapq.heappop(Heapq)
    else:
        heapq.heappush(Heapq,-num)

 

 

설명  (Python)

 

 

힙(Heap)이라는 자료구조에 대해서는 아래 자료구조 개념글에서 자세하게 다루겠다. 

[알고리즘] 자료구조 개념 / 스택, 큐, 덱, 힙 ( Stack, Queue, Deque, Heap)

 

파이썬으로 자료구조 문제는 매우 간편한 편이다. 기본적인 자료구조인 stack, queue, deque, heap은 기본적인 라이브러리에 다 존재하기 때문에 따로 구현할 필요 없이 import하여 사용하면 간단하게 풀이가 가능하다.

 

 

0이아닌 정수 x를 입력시에 x를 heap에 입력하고 0을 입력시에 출력하는 코드를 작성하기만 하면 해결된다.

    if num==0:
        if len(Heapq)==0:print(0)
        else:
            print(-Heapq[0])
            heapq.heappop(Heapq)
    else:
        heapq.heappush(Heapq,-num)

 

 

keypoint 1- heap라이브러리 활용

 

import heapq

heapq.

heapq. 을 입력시에 오른 쪽과 같이 많은 옵션들이 존재한다. 

기본적인 옵션으로 아래 3가지 정도 사용법을 알면 사용시에 문제가 없을 것이다.

 

heapqpush : 힙에 원소를 Push한다.

heapqpop : 힙에 최소 원소를 Pop한다.

heapify : 일반 리스트를 힙으로 변경한다.

 

 

 

keypoint 2- heap모듈의 heap은 최소힙이다.

 

 

파이썬의 내장모듈에 포함되어 있는 heap 모듈은 기본적으로 최소힙이다. 그래서 이와 같이 최대힙 문제를 처음 만나게 되면 난감하게 되는데, 이 때 양/음을 바꾸는 잡기술을 사용하면 된다.

 

heapq.heappush(Heapq,-num)

 

위와 같이 Push시에 num에 -를 붙여 힙을 구성하게 되면 자연스럽게 |num|은 최댓값이 루트에 있게 된다!

※주의 : 출력시에도 -를 붙이는 것을 잊지말자 !

 

 

 

keypoint 2- sys.stdin.readline()

 

시간초과 문제를 해결하기 위해 스택문제와 같이 input()이 아닌 sys.stdin.readline()을 활용하여야 한다.

pop()함수 작동시 인덱스가 줄어드는 내용에 관한 정의를 확인할 수 있다.

입력 속도 sys.stdin.readline() > input()