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

9934번: 완전 이진 트리

[문제]

---

---

[코드]

#중위 순회 문제
#순서가 주어지고 트리를 유추하는 문제
import sys
input = sys.stdin.readline

k = int(input())
squence = list(map(int, input().split()))

trees = [[] for _ in range(k)]

#완전 이진 트리이니까 각 층의 노드는 중간의 값
def binary_tree(array, depth):
    mid_index = len(array) // 2
    trees[depth].append(array[mid_index])
    #만약 input_array가 길이가 1이라면 해당 재귀 종료
    if len(array) == 1:
        return
    #왼쪽 노드부터 먼저 추가 되어야 하니까
    binary_tree(array[:mid_index], depth + 1)
    binary_tree(array[mid_index+1:], depth + 1)


#재귀 함수 0 층부터 실행
binary_tree(squence, 0)
for tree in trees:
    print(*tree)

 

---

[해설]

어제 풀어 보았던 이진 트리 탐색 문제의 변형이다

어제 문제의 경우 트리가 주어지고 탐색 순서를 정답으로 찾는 것이 목적이었다면

이번 문제는 탐색 순서가 주어지고 트리를 유추하는 문제이다

 

해당 문제의 핵심은 아래 2개로 요약할 수 있다

1. 중위순회 tree  - 문제의 조건이 중위 순회이다

2. 완전이진트리 - 트리의 모양이 왼쪽만 있는 경우가 존재하지 않고 왼쪽 노드가 있으면 오른쪽 노드도 존재하는 완전이진트리이다

 

위 두가지의 핵심을 이용하면 문제 해결을 쉽게 정의할 수 있다

바로 주어진 순서에서 중앙 값이 첫 번째 노드인 것이다

 

즉, 2번 예제를 예시로 사용하면

input:

3
1 6 4 3 5 2 7

이니까 여기서 첫번째 노드의 값은 3이 된다

그리고 2번째 층의 왼쪽 노드는 중앙값 바로 앞값까지 인덱싱 된 배열에서 중앙값이 된고

2번째 층의 오른쪽 노드는 중앙값 다음값 부터 마지막 값까지 인덱싱 된 배열에서 중앙값이 된다

 

쉽게 숫자로 표현하면

1층 - 1 6 4 3 5 2 7 

2층(왼) : 1 6 4, 2층(오) : 5 2 7

3층(왼왼) : 1, 3층(왼오) : 4, 3층(오왼) : 5, 3층(오오) : 7

 

따라서 정답은

3
6 2
1 4 5 7

인것이다

 

이를 로직으로 구성하면 다음과 같다

def function(input배열, 층):
	중앙값 계산
    배열의 중앙값에 해당하는 값을 해당 층에 추가
    
    그리고 만약 배열의 길이가 1이라면 재귀 종료
    
    왼쪽 : function(재귀 중앙값 이전까지 인덱싱한 배열, 층+1)
    오른쪽 : function(재귀 중앙값 이후부터 인덱싱한 배열, 층+1)

 

그럼 한번 코드로 직접 구현해보자

#중위 순회 문제
#순서가 주어지고 트리를 유추하는 문제
import sys
input = sys.stdin.readline

k = int(input())
squence = list(map(int, input().split()))

trees = [[] for _ in range(k)]

우선 tree의 층을 k변수로 입력받고

탐색 순서를 list로 저장한다

 

그리고 k만큼 이중리스트를 생성한다 -> ex) k==3 ,   trees = [ [ ], [ ], [ ] ]

 

#완전 이진 트리이니까 각 층의 노드는 중간의 값
def binary_tree(array, depth):
    mid_index = len(array) // 2
    trees[depth].append(array[mid_index])
    #만약 input_array가 길이가 1이라면 해당 재귀 종료
    if len(array) == 1:
        return
    #왼쪽 노드부터 먼저 추가 되어야 하니까
    binary_tree(array[:mid_index], depth + 1)
    binary_tree(array[mid_index+1:], depth + 1)

그리고 재귀함수를 활용할 것이기 때문에 위와 같이 함수를 정의해준다

함수의 input은 탐색 순서 배열, 현재 층이다

 

함수 내부의 작동 원리는 다음과 같다

우선 input으로 들어온 배열의 중앙값 인덱스를 구해준다 - input 배열 길이를 2로 나누어준다

그리고 앞에서 만들어 놓은 trees에 해당 층 위치에 중앙값을 추가해준다

 

그리고 난 이후 재귀 종료 규칙을 설정하는데 만약 인풋 배열의 길이가 1이라면 해당 재귀를 종료한다

 

아니라면 밑에 재귀가 실행되는데

우리가 하는 것은 중위순회 이기 때문에

아래층의 왼쪽 노드가 먼저 trees에 추가되어야 한다

 

따라서 중앙값 앞에 값까지 인덱싱 된 배열을 input으로 넣어주고 해당층의 1층 추가된 층을 input으로 넣어 재귀를 실행한다 - 왼쪽 자식 노드 추가

 

그리고 중앙값 이후의 값부터 인덱싱 된 배열을 input으로 넣고 해당층의 1층이 추가된 층을 input으로 넣어 재귀를 실행한다 - 오른쪽 자식 노드 추가

 

#재귀 함수 0 층부터 실행
binary_tree(squence, 0)
for tree in trees:
    print(*tree)

이렇게 만들어진 재귀함수를 0층부터 시작시키면 trees에 tree가 저장될 것이다

이후 for 문을 통해서 1층 부터 순서대로 출력해주면 정답이 나온다