CodeDrive

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

1. 배열에 자연수 x를 넣는다.

2. 배열에서 가장 큰(작은) 값을 출력하고, 그 값을 배열에서 제거한다.

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

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

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

 python에는 우선순위큐(힙)을 지원하는 heapq라는 모듈이 있다.python에서는 default로 최소 힙을 지원하기 때문에 최소 힙 문제에서는 모듈의 함수를 그대로 사용하면 되지만 최대 힙이나 절대값 힙과 같은 경우에는 별도의 스킬이 필요하다. 

 이 문제에서 사용하는 heapq의 함수는 heapify(), heappop(),heappush()가 있다. heapify(arr)는 일반 배열을 힙 구조를 가지는 배열로 만드는 함수로써 자동으로 배열 내 원소의 변동(추가, 삭제)가 있을 때마다 새로 힙 구조를 만든다. heappop(arr)는 arr에서 제일 위에 있는(제일 작은) 값을 빼내는 함수이고, heappush(arr,item)은 arr에 item을 넣고 힙 구조를 재배열하는 함수이다.

 최소 힙을 최대힙으로 바꾸기 위해서 값을 넣을 때 그냥 값을 넣는 것이 아니라 (-item,item)과 같은 방식으로 값을 넣는다. 힙 구조를 -item을 기준으로 정렬한다. 단순히 생각하면 "최소 힙으로 정렬한 것을 뒤집었다"라고 생각하면 된다. 따라서 이렇게 값을 넣었으므로 뺀 뒤에 [1]과 같은 방식으로 값을 접근해야 원래의 값을 얻는다.

 최대 힙과 같은 방식으로 절대값 힙도 (abs(item),item)으로 정렬하면 된다.

또한 python3로 제출하면 시간초과가 발생해서 pypy3로 제출해서 시간초과문제를 해결하였습니다.

[2019.07.29 수정] 문제가 재채점 되었더니 시간초과가 발생하였다. 따라서 input() -> sys.stdin.readline().rstrip() 으로 바꾸어서 해결하였다. (import sys 필요)