9934

날짜 : 2023. 06. 27

사용 언어 : python

 

문제

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

 

 

코드

import sys


def inorder(subtree, depth):
    # print(subtree, depth)
    if len(subtree) == 0: return
    mid = int(len(subtree) // 2)
    if depth < (K-1) : inorder(subtree[:mid], depth + 1)
    res[depth].append(subtree[mid])
    if depth < (K-1) : inorder(subtree[mid+1:], depth + 1)
    return

K = int(sys.stdin.readline())  # 최종 깊이
tree = list(map(int, sys.stdin.readline().split()))

res = [[] for _ in range(K)]

inorder(tree, 0)

for i in res:
    print(*i)

 

 

풀이

- 조건에 따라 입력받은 후 Inorder 방식으로 탐색한다.

- 각 depth마다 저장해야 하므로 parameter에 depth를 따로 지정하고, 현재 함수의 subtree 리스트의 mid값이 해당 트리의 root가 되기 때문에 이를 구한 후 Left - Root - Right 순서로 처리한다.

- Root의 경우에는 res 리스트의 depth 에 맞게 append 하는 방식으로 넣는다.

- 다만, 주어진 트리가 full binary tree 가 아니기 때문에 서브트리가 비어있는 경우 리턴하는 케이스를 넣고 진행한다.

 

 

알게된 점

-  인덱스를 넣어서 진행하려 했지만 계속 뭔가가 안맞았다.

- 그래서 아예 서브트리를 매개변수로 넣어서 전달하는 것으로 방향을 틀었고, 서브트리가 비어있는 케이스를 적용하니까 바로 문제는 풀렸다.

 

 

참고 사이트

-