백준 1927번 <파이썬> (힙에 대해 공부하기)

1. 힙이란 무엇인가

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

 

A가 B의 부모 노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다

최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙

최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

이러한 속성으로 인해 힙에서는 가장 낮거나 혹은 가장 높은 우선순위를 가지는 노드가 항상 루트에 오게 되고

이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

 

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

heap이라는 빈 리스트를 생성하고 그 리스트에 heappush라는 heapq모듈의 메소드를 이용해 숫자를 집어넣는 방법이다.

result = heapq.heappop(heap)

 heappop함수는 가장 작은 원소를 힙에서 제거함과 동시에 그 결과값을 리턴한다.

 

만약 가장 작은 원소를 제거하지 않고 가져오고 싶다면

result2 = heap[0]

이런식으로 인덱싱을 통해 접근하면 된다.

 

2. 문제

문제에서 출력은 0이 입력됐을 경우의 출력이 된다. 이때 출력은 기본적으로 배열에서 최솟값을 출력하고

만약 배열이 비어있다면 0을 출력하게 된다.

 

입력의 경우 첫줄에 입력하는 숫자는 몇번을 반복해줄지 결정하는 숫자이고

0이 입력할 경우 위에서 설명한 방법대로 출력을 하고 0 이외의 자연수가 입력될 경우 힙에 해당하는 자연수를 push해준다 (이때 음수는 입력되지 않는다)

 

import heapq
import sys

input = sys.stdin.readline

N = input(input())
heap = []
for i in range(N):
    x = int(input())
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap,x)

1. heap이라는 빈 리스트를 만들어 준 뒤 입력받은 숫자만큼 반복하기 위해 for문을 돌려 준다.
2. 이때 각각 x에 숫자를 반복해서 입력 받는다.
3. 주어진 조건에 따라 x가 0일 경우 혹은 0이 아닐경우를 나눈다.
4. 먼저 x가 0일 경우 힙이 비어있는지 안비어있는지를 먼저 판단한다.
5. 힙이 비어있다면 문제의 조건에 맞춰 0을 출력한다
6. 힙이 비어있지 않다면, 힙에서 최소값을 출력함과 동시에 제거한다 (heappop은 최소값을 리턴하면서 제거함)
7. x가 0이 아닐경우에는 heap이라는 리스트에 x값을 입력해준다.