[복기] 5639번: 이진 검색 트리

문제

백준 5639번: 이진 검색 트리

알고리즘 분류

• 그래프 이론
• 재귀
• 트리

나의 풀이(런타임에러)

간단하게 전위 검색 배열을 이진 검색 트리로 바꾼 후, 이진 검색 트리에서 후위 검색하였다. 로직 자체는 맞다. 후위 검색하는거야 재귀로 짜면 그만이다. 전위 검색 배열을 이진 검색 트리로 바꾸기 위해서는 트리 배열을 만든 후, 값에 맞는 인덱스를 찾아주면 된다. 문제는 트리 배열을 생성하는 부분 에서 생겼다. 예제에서는 입력값이 적어서 문제가 없었는데 제출하고보니 백준 런타임에러(OverflowError)가 발생했다. 입력값의 개수에 비례하게 트리 배열을 생성했는데, 입력된 노드의 개수가 10000개일 때 최악의 경우 트리 배열은 2^10000개가 필요해진다. 당연히 int 연산에서 터지고, sys.MAXINT를 써도 메모리가 터질 것이다.

배열을 할당하는 방식은 안된다.

코드

import sys
sys.setrecursionlimit(10**9)

def visit_postorder(bt, idx):
    if bt[idx] == 1000000:
        return
    
    visit_postorder(bt, idx*2)
    visit_postorder(bt, idx*2+1)
    print(bt[idx])
    return

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

n = len(t)
bt = [1000000] * (2**9)
idx = 1
for i in range(n):
    bt[idx] = t[i]
    if i < n-1:
        parent = 1
        while True:
            if bt[parent] == 1000000:
                idx = parent
                break
            if bt[parent] > t[i+1]:
                parent = 2*parent
            else:
                parent = 2*parent + 1

visit_postorder(bt, 1)

솔루션: 재귀

전위 검색 배열 -> 이진 검색 트리 -> 후위 검색 배열의 2단계로 진행된 내 풀이과정과는 달리, 솔루션에서는 재귀를 사용해서 한번에 해결했다. 굳이 따지자면 분할정복의 개념이다. root를 기반으로 작은 값들을 왼쪽 서브트리로 만들고, 큰 값들은 오른쪽 서브트리로 만든다. 재귀 호출 후에는 후위 검색을 위해 print(root)를 한다.

내 풀이과정이 문제가 생길거라고는 생각했고, 2단계를 거치지않고 한번에 푸는 방법이 있을거라 생각했지만, 솔루션 풀이과정은 역시 대단하다. 재귀를 이용한 트리 순회는 생각도 못해봐서 더 신기하다.

import sys
sys.setrecursionlimit(10**9)

preorder = []

def postorder(start, end):
    if start >= end:
        return
    root = preorder[start]

    if preorder[end - 1] <= root:
        postorder(start + 1, end)
        print(root)
        return

    idx = 0
    for i in range(start + 1, end):
        if preorder[i] > root:
            idx = i
            break
    postorder(start + 1, idx)
    postorder(idx, end)
    print(root)
    
while True:
    try:
        preorder.append(int(input()))
    except:
        break


postorder(0, len(preorder))