[골드 V] 5639번. 이진 검색 트리

 문제 

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

5639번: 이진 검색 트리

 사용 언어 

Python3

 풀이 과정 

이거야말로 저번에 풀었던 4256번. 트리 문제와 비슷하다고 생각했는데 한 번에 풀지 못했다...

그 문제는 그냥 트리이고 이건 이진 트리임을 이용한 문제인데 이진 트리의 개념은 알고 있었지만 탐색을 어떻게 해야할지...막막쓰..

 

그래서 다른 블로그의 도움을 받아😥 맞았습니다!!

처음 제출 후 while True: 를 while count <= 10000: 으로 변경해봤는데 아마도 count += 1 하는 연산 때문에 더 시간이 많이 걸리더라.

 제출 답안 

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

tree = []
while True:
    try:
        num = int(input())
    except:
        break
    tree.append(num)

def postorder(start, end):
    # 시작이 끝보다 크면 리턴
    if start > end:
        return
    mid = end + 1
    # 서브 트리 찾기
    for i in range(start + 1, end + 1):
        # 루트보다 크면 오른쪽 서브 트리
        if tree[start] < tree[i]:
            mid = i
            break
    
    postorder(start + 1, mid - 1) # 왼쪽 서브 트리
    postorder(mid, end) # 오른쪽 서브 트리
    print(tree[start])

postorder(0, len(tree) - 1)

 

 공부한 내용 

이진 검색(탐색) 트리

이진 트리란 하나의 노드에 최대 두 개의 자식 노드를 가지는 트리이고, 그 중에 이진 검색(탐색) 트리는 다음의 조건을 만족하는 이진 트리를 의미한다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

 

 

출처: https://honggom.tistory.com/40