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

🔗 문제 링크

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

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

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

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

테스트 케이스

예제 입력	예제 출력
50 30 24 5 28 45 98 52 60	5 28 24 45 30 60 52 98 50

---

💻 나의 코드

1st Code:

import sys
sys.setrecursionlimit(10**6)

class Node:
    def __init__(self, key, value, left, right):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

class bst:
    def __init__(self):
        self.root = None

    def add(self, key, value):
        def add_node(node, key, value):
            if key == node.key:
                return False
            elif key < node.key:
                if node.left is None:
                    node.left = Node(key, value, None, None)
                else:
                    add_node(node.left, key, value)
            else:
                if node.right is None:
                    node.right = Node(key, value, None, None)
                else:
                    add_node(node.right, key, value)
            return True

        if self.root is None:
            self.root = Node(key, value, None, None)
            return True
        else:
            return add_node(self.root, key, value)

    def dump(self, reverse = False): # post-order
        def print_subtree(node):
            if node is not None:
                print_subtree(node.left)
                print_subtree(node.right)
                print(node.key)
                
        print_subtree(self.root)

input = sys.stdin.readline

arr = list()
while True:
    try:
        arr.append(int(input().strip()))
    except:
        break

tree = bst()
for i in arr:
    tree.add(i, i)
tree.dump()

이진 탐색 트리 클래스를 구현해서 트리를 생성해 후위 순회를 돌렸지만 메모리 초과로 실패했다.😔

2nd Code:

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

def post(arr):
    left = list()
    right = list()
    
    for i in range(1, len(arr)):
        if arr[i] < arr[0]:
            left.append(arr[i])
        else:
            right.append(arr[i])
            
    if left: post(left)
    if right: post(right)
    print(arr[0])

arr = list()

while True:
    try:
        arr.append(int(input().strip()))
    except:
        break

post(arr)

재귀로 푼다는 생각은 못하고 있었는데, 알고리즘 분류에 재귀가 있는 것을 보고 재귀로 구현해봤더니 맞았습니다!!를 받을 수 있었다.

---

Another Code?

다음은 doyong님의 코드이다.

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.read
preorder = list(map(int, input().split()))
idx = 0

def build_tree(lower, upper):
    global idx
    if idx >= len(preorder):
        return None
    
    val = preorder[idx]
    if not (lower < val < upper):
        return None

    idx += 1
    node = Node(val)
    node.left = build_tree(lower, val)
    node.right = build_tree(val, upper)
    return node

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

root = build_tree(float('-inf'), float('inf'))
postorder(root)

 

트리 클래스를 구현하셨는데, 내가 처음에 작성한 코드와는 다르게 간결하게 구현되어 있고, 실제로 메모리 사용량과 실행 시간도 재귀로 구현했던 내 코드보다 몇 배는 더 좋았다.

 

책에 적혀 있는 코드만 그대로 보고 따라서 치는 것이 아니라, 어떻게 하면 시간/공간적으로 얼마나 효율적으로 구현할 수 있을 지 고민을 하면서 코드를 구현하는 연습이 필요한 것 같다.😇