[Python] 백준5639 이진 검색 트리

24 May 2023 in Study on Algorithm

백준5639 이진 검색 트리 링크

문제

예제 입력

---

코드

import sys
sys.setrecursionlimit(10 ** 6)

# 이진 탐색(부모 노드=target를 받아 좌/우 지점을 찾음)
def binaryS(st, end, target):
    while st <= end:
        mid = (st + end) // 2
        if arr[mid] <= target:
            st = mid + 1
        else:
            end = mid - 1
    return end

# 후위 순회를 활용하여 재귀적으로 구하기
def sol(st, end):
    # 범위가 0이 될 때마다 종료
    if st > end:
        return

    # 부모 노드의 값
    parent = arr[st]
    
    # 다음 부모 노드 위치를 찾으며 분할 정복
    idx = binaryS(st, end, parent)
    # print(parent) = 전위 순회
    sol(st + 1, idx)
    # print(parent) = 중위 순회
    sol(idx + 1, end)
    print(parent)
    # res.append(parent)
    return

arr = []
# res = []
# 입력(EOF 처리 = Ctrl + Z)
lines = sys.stdin.readlines()
for line in lines:
    arr.append(int(line))

sol(0, len(arr)-1)
# print(*res, sep="\n")

설명

파이썬을 통해서 사용자로부터 입력받아 재귀알고리즘을 사용하여 이진 검색 트리를 정복 분할하여 구현했습니다.

---

결과