[n9934] 완전 이진 트리 in python

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

9934번: 완전 이진 트리

---

(처음 든 생각)

2중 for문으로 되려나...

-> for문 + while문으로 시도했으나 깔끔하게 실패!

 

좀 더 고민하며 삽질하다가

결국 풀이 찾아보기..

 

문제 자체로만 읽고 순서를 어떻게 처리해줘야하지 고민만 했는데!

다른 블로그 풀이를 보니까

이렇게 깔끔하게 풀리는 걸..

아직 갈길이 멀다는 걸 느꼈던 하루 :) 

 

---

(풀이)

이 문제는 재귀함수로 풀어주면 이렇게 깔끔한 코드가 나온다아.... 

inorder 함수에 input_array랑 depth 깊이를 계속 넣어주면서

input_array의 길이가 1이 될 때까지 재귀함수 돌리기!!

 

배열을 2로 나눈 몫이 루트 노드...!

이걸 왜 몰랐지;;

위 예시에서 보면

3을 기준으로 왼쪽은 왼쪽 자식 트리, 오른쪽은 오른쪽 자식 트리로... 보면 된다.

 

이걸 파악했더라면 좀 더 쉽게 풀 수 있었을 것 같다 :) 

-> 그냥 문제보고 음.. 순서를 모르는구나?

이렇게만 생각했지 배열 중간에서부터 시작할 생각은 꿈에도 못했다~!

 

앞으로 전위순회할 땐 한 번씩 떠올려볼 것......★

 

k = int(input())
array = [[] for _ in range(k)]  # idx 0은 데모 (무시하기)
input_array = list(map(int, input().split()))


def inorder(input_array, depth):
    # len이 1이 될때까지 계속 나눠줌
    if len(input_array) == 1:
        return
    mid = len(input_array) // 2
    array[depth].append(input_array[mid])
    inorder(input_array[:mid], depth + 1)  # 왼쪽 트리
    inorder(input_array[mid + 1:], depth + 1)  # 오른쪽 트리


inorder(input_array, 0)
for i in array:
    print(*i)

 

 

---

참고 블로그

https://hillier.tistory.com/108?category=973587 

[백준 9934] 완전 이진 트리 (python)