[백준/Python] 11279번 : 최대 힙

문제 정보

제목 : 최대 힙

번호 : 11279번

사용 언어 : Python

문제 링크

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

11279번: 최대 힙

 

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

 

문제

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

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

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

 

입력

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

 

출력

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

 

입출력 예제

---

나의 풀이

최소 힙 문제와 유사한 문제였습니다. 차이접은 heapq 모듈은 최소 힙의 형태이므로 -x로 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀌게 됩니다. 이를 이용해 원소를 추가할 때 (-x, x)와 같은 튜플 형태로 저장하여 최대값을 구할 수 있도록 했습니다.

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

N만큼 반복하는 for 루프를 이용해 연산에 대한 정보를 나타내는 수를 입력받아 정수형으로 변환 후 x에 저장합니다. if문을 이용해 x가 0일때와 자연수일때를 나누어 처리합니다. 배열이 비어있다면 0을 출력하고 그렇지 않다면 max_heap을 heappop()한것 중 인덱스 1의 값을 answer에 저장하고 출력합니다. 자연수가 x에 저장되면 max_heap에 (-x, x)형태로 저장합니다.

 

코드

import heapq
import sys

max_heap = []
input = sys.stdin.readline
N = int(input())
for i in range(N) :
    x = int(input())

    if ( x == 0 ) :
        answer = 0
        if (not max_heap) :
            print(answer)
        else :
            answer = heapq.heappop(max_heap)[1]
            print(answer)
    else :
        heapq.heappush(max_heap, (-x, x) )