EDOC 2023-W 7회차 정모 (이진 트리 / 세그먼트 트리)

A. 완전 이진 트리 (백준 9934번)

 

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

 

#python

import sys
input = sys.stdin.readline

k = int(input())
visit = list(map(int, input().split()))
tree = {}

for i in range(1, pow(2, k-1)):
    tree[i] = [i*2, i*2 + 1, 0]

for i in range(pow(2, k-1), pow(2, k)):
    tree[i] = ['.', '.', 0]

def inOrder(now):
    global i
    if now != '.':
        inOrder(tree[now][0])
        tree[now][2] = visit[i]
        i += 1
        inOrder(tree[now][1])

i = 0
inOrder(1)

level = 1
for i in range(1, pow(2, k)):
    if i == pow(2, level):
        print()
        level += 1
    print(tree[i][2], end=' ')

저번에 풀었던 전위 순회, 중위 순회, 후위 순회 관련 문제랑은 순서가 반대라고 해야 하나? 그래서 헷갈렸던 문제였다. 그래도 정신만 붙들고 풀면 맞힐 수 있었던 문제! (정답)