[baekjoon] 백준 9934번(파이썬): 완전 이진 트리

문제

9934번: 완전 이진 트리

알고리즘

- 분할 정복을 통해 문제를 수행한다.

- 문제를 보면 중위 순환을 통해 빌딩을 방문한 것을 확인할 수 있다.

- 중위 순환이고 완전 이진 트리이기 때문에 중간에 있는 노드가 루트 노드가 된다.

- 루트 노드를 찾고 왼쪽 서브 노드와 오른쪽 서브 노드를 나눠 각 트리를 재귀적으로 탐색한다.

코드

import sys
sys.setrecursionlimit(10 ** 9)


# 분할 정복
def divide(start, end, lev):
    # 시작 점과 끝 점이 크로스되면 리턴
    if start > end:
        return
    center = (start + end) // 2 # 루트 노드
    level[lev].append(n[center]) # 루트 노드를 레벨의 따라 리스트에 추가
    divide(start, center - 1, lev + 1) # 왼쪽 서브 트리의 루트 노드를 재귀적으로 탐색
    divide(center + 1, end, lev + 1) # 오른쪽 서브 트리의 루트 노드를 재귀적으로 탐색


k = int(sys.stdin.readline())
n = list(map(int, sys.stdin.readline().split()))
level = [[] for _ in range(k)]

# 분활 탐색
divide(0, len(n) - 1, 0)

# 각 레벨의 따라 노드를 출력
for i in level:
    print(*i)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법