💻 백준 5639번: 이진 검색 트리

문제 소개 🧐

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

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

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다.

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

입력 📝

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

출력 📤

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

제한 ❌

  • 시간 제한: 1초
  • 메모리 제한: 256MB

첫 번째 시도: 클래스를 이용한 트리 구현 😭

Idea

일단 입력을 통해 트리를 만들고, 그걸 후위 순회해야겠다.

Code

import sys

sys.setrecursionlimit(300000)

class Node:
    val: int
    left: 'Node'
    right: 'Node'

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

def insert_node(root: Node, new_node: Node):
    if new_node.val < root.val:
        if node.left == None:
            node.left = new_node
        else:
            insert_node(node.left)

    else:
        if node.right == None:
            node.right = new_node
        else:
            insert_node(node.right)

    
def post_search(node: Node):
    if node.left == None and node.right == None:
        return print(node.val)

    if node.left != None:
        post_search(node.left)
    if node.right != None:
        post_search(node.right)
    
    return print(node.val)

root = Node(int(sys.stdin.readline().rstrip()))

lines = sys.stdin.readlines()

for line in lines:
    node = Node(int(line.rstrip()))
    Node.insert_node(val=node, root=root)

post_search(root)

Result

  • 결과: 시간초과 😭
  • 객체를 계속 만들기 때문에 그 부분에서 시간이 좀 걸리는 듯 하다.

두 번째 시도: 분할 정복 ✨

Idea

스택을 이용해 분할 정복 해봐야겠다.

Code

import sys
sys.setrecursionlimit(300000)

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

def postorder(start, end):
    if start > end:
        return
    
    root = preorder[start]
    
    # 오른쪽 서브트리 시작점 찾기
    idx = start + 1
    while idx <= end and preorder[idx] < root:
        idx += 1
    
    # 왼쪽, 오른쪽 재귀
    postorder(start+1, idx-1)   # 왼쪽
    postorder(idx, end)         # 오른쪽
    print(root)

postorder(0, len(preorder)-1)

Result

  • 결과: 성공! 🎉
  • 트리를 명시적으로 만들지 않고 배열 인덱스를 이용해 분할 정복을 적용하니 통과할 수 있었다.

개선할 부분 🤔

  • 알고리즘, 파이썬에서 트리 구현에 대해 더 알아봐야겠다.

전위 순회 결과를 보고 서브트리를 나누는 아이디어를 떠올리는 것이 핵심이었다. 재귀와 분할 정복에 대한 이해를 깊게 할 수 있는 좋은 문제였다.

⁂