[SWEA / PYTHON] 2930. 힙

import os
import sys


current_file = os.path.basename(__file__)[:-3]
sys.stdin = open(f"input/{current_file}_input.txt", "r", encoding="utf-8-sig")


import heapq

result = []

T = int(input())

for case in range(1, T + 1):
    N = int(input())
    heap = []
    ans = []
    for _ in range(N):
        cmd = list(map(int, input().split()))

        if cmd[0] == 1:
            heapq.heappush(heap, -cmd[1])
        else:
            if len(heap) > 0:
                ans.append(-heapq.heappop(heap))
            else:
                ans.append(-1)
    
    result.append(f"#{case} {' '.join(list(map(str, ans)))}")


for _ in result:
    print(_)


output = open(f"input/{current_file}_output.txt", "r").readlines()
output = [line.strip() for line in output]

print("------------------- 오답 ------------------ ( 이 아래로 출력이 없으면 정답)")

for r, o in zip(result, output):
    if r != o:
        print(f"정답 : {o},     오답 : {r}")

풀이.

처음에는 힙 자료구조를 직접 배열로 만들어서 풀어보려고 했으나, 10개의 테스트 케이스에서 9개만 통과하거나, 계속해서 시간초과가 발생하여 heapq 라이브러리를 이용해서 해결했다.

최대 힙은 부모 노드의 값이 자식 노드보다 반드시 크거나 같아야 한다.
자식 노드 간의 대소 관계는 없다.

삽입 연산시, 가장 마지막 노드에 삽입 후 부모 노드와 비교하여 스왑 하는 식으로 구현했고,
삭제 연산시, 루트 노드 값을 마지막 노드 값으로 대체하여, 자식 노드들과 비교하여 최대 힙을 만족하도록 구현했다.

근데 시간초과가 발생하더라...