[WEEK 03] 백준 5639번 - 이진 검색 트리 (Python)

백준 5639 이진 검색 트리

 

 

이진 검색 트리의 전위 순회 결과를 토대로 후위 순회 결과를 출력하는 프로그램을 만드는 문제이다. 이진 검색 트리의 조건은 다음과 같으며, 이를 이용해 문제를 풀 수 있다.

 

 

이진 검색 트리(binary search tree)는 모든 노드가 다음 조건을 만족해야 한다.

• 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다.
• 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다.

 

 

처음에는 전위 순회 결과를 토대로 트리를 복구한 다음, 후위 순회 결과를 출력하는 방식으로 풀이를 시도 했으나, 시간 초과와 메모리 초과가 발생하였다.

 

전위 순회 결과의 첫번째 요소는 이진 검색 트리의 루트 노드이다. 이를 시작점으로 하여 각 노드들과의 대소 관계 비교를 통해 트리의 구조를 파악하고, 후위 순회 결과를 출력한다.

 

입력값의 개수를 모르기 때문에 while문을 통해 입력을 받되, try except로 예외 처리를 하여 입력이 있을 때까지만 입력을 받도록 한다.

while True :
    try :
        preorder.append(int(sys.stdin.readline()))

    except :
        break

입력값이 없을 경우, append 함수의 인수가 없기 때문에 TypeError가 발생한다. 예외가 발생하면, except로 이동하여 해당 while문을 중단한다. 아래는 try except에 대한 설명이다.

 

try except 문

 

try except의 구조는 다음과 같다. 이는 예외가 발생했을 때도 스크립트 실행을 중단하지 않고 계속 실행하게 해주는 예외 처리 방법이다.

try :
	실행할 코드
except :
	예외가 발생했을 때 처리하는 코드

예외(exception)란 코드를 실행하는 중에 발생한 에러를 뜻한다. 실행할 코드에서 예외가 발생하면, 해당 줄에서 코드 실행을 중단하고 바로 except로 가서 코드를 실행한다.

 

ZeroDivisionError, AttributeError, NameError, TypeError 등 다양한 에러들도 모두 예외이다. 에러는 에러명과 함께 에러 메세지가 뜬다. except 뒤에 예외 이름을 지정해서 특정 예외만 처리할 수도 있고, 변수를 통해 에러 메세지를 받아올 수도 있다.

 

 

백준 5639 이진 검색 트리의 풀이 코드는 다음과 같다.

import sys

sys.stdin = open('input.txt', 'r')

sys.setrecursionlimit(10**6)

preorder = []

while True :
    try :
        preorder.append(int(sys.stdin.readline()))

    except :
        break

def postorder(start, end) :

    mid = 0

    if start > end :
        return

    for i in range(start + 1, end + 1) :
        if preorder[start] < preorder[i] :
            mid = i
            break

    else :
        mid = end + 1
        
    postorder(start + 1, mid - 1)
    postorder(mid, end)
    print(preorder[start])

postorder(0, len(preorder) - 1)

주목한 노드에 대해 오른쪽 서브 트리와 왼쪽 서브 트리로 나누는 기준을 mid라는 변수로 지정하였다.