취알스 10주차 우선순위 큐, 힙, 트리 요약 - 2/4

14698 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

• 우선순위 큐, 그리디 알고리즘 이용
• 문제가 복잡해보이지만 greedy하게 풀면 아주 쉽게 풀 수 있음.

import heapq
import sys
input = sys.stdin.readline
t = int(input())
while(t>0):
    que = []
    n = int(input())
    temp = list(map(int, input().split()))
    for i in range(n):
        heapq.heappush(que, temp[i])
    answer = 1
    while len(que)>1:
        no1 = heapq.heappop(que)
        no2 = heapq.heappop(que)
        answer  = answer * no1 * no2
        heapq.heappush(que, no1 * no2)
    print(answer%1000000007)
    t-=1

1991 트리 순회

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node
# 전위 순회
def pre_order(node):
    print(node.data, end='')
    if node.left_node != None:
        pre_order(tree[node.left_node])
    if node.right_node != None:
        pre_order(tree[node.right_node])
#중위 순회
def in_order(node):
    if node.left_node != None:
        in_order(tree[node.left_node])
    print(node.data, end='')
    if node.right_node != None:
        in_order(tree[node.right_node])
#후위 순회
def post_order(node):
    if node.left_node != None:
        post_order(tree[node.left_node])
    if node.right_node != None:
        post_order(tree[node.right_node])
    print(node.data, end='')

n = int(input())
tree = {}

for i in range(n):
    data, left_node, right_node= input().split()
    if left_node ==".":
        left_node = None
    if right_node == ".":
        right_node = None
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])