문제 링크
https://www.acmicpc.net/problem/11279
구현
내 생각대로 최대 힙을 구현했는데, 시간이 굉장히 오래 걸렸다. 저수준 출력을 사용하지 않으면 통과되지 않을 정도였다.
80ms선에서 맞춘 사람들의 코드를 보니 heapq 모듈을 많이 사용하는 것 같았다. 나중에 사용해봐야겠다.
from sys import stdin, stdout
from collections import deque
input = lambda : int(stdin.readline())
if __name__ == '__main__':
n = int(input())
max_heap = deque()
answer_list = []
for _ in range(n):
command = input()
if command == 0:
if max_heap:
answer_list.append(max_heap.popleft())
max_heap.rotate(1)
idx = 0
child1 = idx * 2 + 1
child2 = idx * 2 + 2
while child1 < len(max_heap) or child2 < len(max_heap):
if child1 < len(max_heap) and child2 < len(max_heap):
if max_heap[child1] < max_heap[child2]:
if max_heap[idx] < max_heap[child2]:
max_heap[idx], max_heap[child2] = max_heap[child2], max_heap[idx]
idx = child2
else:
break
else:
if max_heap[idx] < max_heap[child1]:
max_heap[idx], max_heap[child1] = max_heap[child1], max_heap[idx]
idx = child1
else:
break
elif child1 < len(max_heap):
if max_heap[child1] > max_heap[idx]:
max_heap[idx], max_heap[child1] = max_heap[child1], max_heap[idx]
idx = child1
else:
break
elif child2 < len(max_heap):
if max_heap[child2] > max_heap[idx]:
max_heap[idx], max_heap[child2] = max_heap[child2], max_heap[idx]
idx = child2
else:
break
child1 = idx * 2 + 1
child2 = idx * 2 + 2
else:
answer_list.append(0)
else:
max_heap.append(command)
idx = len(max_heap) - 1
parrent = (idx - 1) // 2
while parrent >= 0 and idx >= 0 and idx != parrent and max_heap[parrent] < max_heap[idx]:
max_heap[idx], max_heap[parrent] = max_heap[parrent], max_heap[idx]
idx = parrent
parrent = (idx - 1) // 2
stdout.write('\n'.join(map(str, answer_list)))