[백준 5639 파이썬] 이진 검색 트리 (골드 5, 트리)

알고리즘 유형 : 트리(순회)
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# 이진 탐색(target보다 작은 직전의 수 또는 target과 같은 수의 idx 리턴)
def binarySearch(start, end, target):
    while start <= end:
        mid = (start + end) // 2
        if preorder[mid] <= target:
            start = mid + 1
        else:
            end = mid - 1
    
    return end

# 후위 순회를 활용하여 재귀적으로 전위 순회 구하기
def postorder(start, end):
    # 전위 순회를 구하려는 범위가 0이 될 때마다 종료
    if start > end:
        return
    
    # 후위 순회의 마지막 노드를 전위 순회의 첫 번째 노드로 삼기
    parent = preorder[start]
    
    # 루트 노드 직전의 작은 수의 위치를 이분 탐색으로 찾는다.
    # 그 것을 포함한 왼쪽 부분의 수 들이 왼쪽 서브트리의 후위 순회
    # 오른쪽이 오른쪽 서브트리의 후위 순회이다.
    # 그 두 개를 이용하여 왼쪽, 오른쪽 서브트리의 전위 순회를
    # 구하여 합치는 분할 정복을 행하면 된다.
    parent_idx = binarySearch(start, end, parent)
    left_start = start + 1
    left_end = parent_idx
    right_start = parent_idx + 1
    right_end = end
    
    postorder(left_start, left_end)
    postorder(right_start, right_end)
    result.append(parent)
    return

preorder = []
result = []

# 입력(EOF 처리)
lines = sys.stdin.readlines()
for line in lines:
    preorder.append(int(line.strip()))

postorder(0, len(preorder)-1)
print(*result, sep="\n")

풀이 요약

1. 트리가 이진 검색 트리이고 후위 순회가 주어진다면 중위 순회 없이도 전위 순회를 구할 수 있다.

2. 반복되는 구조를 활용하여 분할 정복으로 푼다.

   반복되는 구조는 다음과 같다.

   우선 후위 순회의 마지막 노드를 전위 순회의 첫 번째 노드로 삼는다.(전체 트리에 대한 루트 노드)

   이 후, 후위 순회 리스트에서 그 루트 노드 바로 직전의 작은 노드의 idx를 이분 탐색으로 찾는다.

   그럼 그 수를 포함한 왼쪽 부분은 왼쪽 서브트리의 후위 순회, 오른쪽은 오른쪽 서브트리의 후위 순회이다.

   그 둘을 이용하여 왼쪽, 오른쪽 서브트리의 전위 순회를 구한 후 합하여 전체 트리의 전위 순회를 구한다.

   전체 트리에 대한 수행을 왼쪽, 오른쪽 서브트리로 범위를 줄여 똑같이 행하므로 재귀 구조를 적용할 수 있다.

3. 해당 문제는 입력의 끝이 명시돼있지 않으므로 EOF 처리를 해주자(예외 처리나 readlines로)

배운 점, 어려웠던 점

• 파이썬 EOF 처리 방법 두 가지를 배웠다.

• 트리 순회 경험을 더 쌓을 수 있었고, 이진 검색 트리에 대해 알게 되었다.