[백준/Python] 1927번 : 최소 힙

문제 정보

제목 : 최소 힙

번호 : 1927번

사용 언어 : Python

문제 링크

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

1927번: 최소 힙

 

시간 제한	메모리 제한
1 초 (추가 시간 없음)	128 MB

 

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

 

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

입출력 예제

---

나의 풀이

파이썬 heapq 모듈을 이용해 문제를 해결했습니다. 시간 제한이 1초이기 때문에 입력에 소요되는 시간을 줄이기 위해 sys 라이브러리를 활용했습니다. 요소를 저장할 배열 min_heap 리스트를 생성합니다. 연산의 개수를 받아 정수형으로 변환하여 N에 저장합니다.

N만큼 반복하는 for루프를 이용하여 연산에 대한 정보를 나타내는 수를 입력받아 정수형으로 변환 후 x에 저장합니다. if문을 이용해 x가 0일때와 자연수일때를 나누어 처리합니다. x가 0이라면 가장 작은 값을 출력해야합니다. 배열이 비어있는지 확인 후 비어있다면 0을, 안에 요소가 있다면 그 중 가장 작은 값을 꺼내 출력합니다. x가 자연수라면 x를 min_heap에 저장합니다.

 

 

코드

import heapq
import sys

input = sys.stdin.readline
min_heap = []

N = int(input()) # 연산의 개수
for i in range(N) :
    result = 0
    x = int(input()) # 연산에 대한 정보를 나타내는 정수 x

    if ( x == 0 ) : # x가 0일때
        if (not min_heap) : # 배열이 비어있다면 0 출력
            print(result)
        else : # 가장 작은 값 출력
            result = heapq.heappop(min_heap)
            print(result)
    else : # x가 자연수일때
        heapq.heappush(min_heap,x)