백준 풀이

5639 이진 검색 트리

접근

1. 전위 순회 데이터를 기반으로 이진 탐색트리를 생성한 뒤 우위 순회로 출력한다.
   -> 실패함

2. 전위 순회 데이터를 즉시 후위 순회로 변경하여 출력한다.
   -> 굉장히 복잡함.

풀이

이진 검색 트리를 구성 한 뒤 postorder로 출력하는 코드

이 코드는 시간초과 발생

## 시간 초과 ## 

import sys
sys.setrecursionlimit(10**9)

def insert(value):
    global tree, first_root
    root = first_root
    tree[value] = [None, None]

    while root != None:
        left, right = tree[root]
        if value < root:
            if left == None:
                tree[root][0] = value
                break
            else:
                root = left
        else:
            if right == None:
                tree[root][1] = value
                break
            else:
                root = right


def postorder(root):
    if tree[root][0] != None:
        postorder(tree[root][0])
    if tree[root][1] != None:
        postorder(tree[root][1])
    print(root, end=' ')


preorder = []
while True:
    try:
        value = int(sys.stdin.readline())
        preorder.append(value)
    except:
        break

first_root = preorder[0]
tree = {first_root: [None, None]}
# print(tree)



for node in preorder[1:]:
    insert(node)
# print(tree)

postorder(first_root)

전위 순회를 바로 후위순회로 바꿔 출력하는 풀이

import sys
sys.setrecursionlimit(10**9)


def postorder(start, end):
    # 왼쪽 서브트리에서 왼쪽 서브트리를 찾아가는 범위
    if start > end:
        return

    # start == end가 되는 순간 print문까지 연결된다.
    # 불필요한 자원낭비 방지
    if start == end:
        print(preorder[start])
        return

    # 왼쪽 서브트리의 오른쪽 끝단
    mid = end + 1
    # start ~ end 중 현재 root node보다 큰 값이 나타났을 경우엔 오른쪽 노드에 해당된다.
    # 여기서 걸리는 순간 오른쪽 노드까지 탐색하는 걸 막기 위해 탐색 범위를 줄인다. (end 범위 좁히기)
    for i in range(start + 1, end + 1):
        # 현재 탐색중인 노드의 값이 start에 해당하는 값 (현재 서브트리의 루트노드)보다 크면 오른쪽 서브트리에 해당된다.
        if preorder[i] > preorder[start]:
            mid = i
            break

    postorder(start + 1, mid - 1)  # L
    postorder(mid, end)  # R
    print(preorder[start])  # V


lines = sys.stdin.readlines()
preorder = [int(line) for line in lines]
postorder(0, len(preorder) - 1)

후기

첫 번째 풀이는 보편적으로 시간초과가 발생한다.
같은 기수 동료 중 한명이 이 방법으로 성공했지만 나는 실패했다.

dictionary를 적극적으로 활용했다고 들어서 활용해봤는데 왜인지 25%에서 시간초과가 발생한다.

한쪽으로 쏠리는 경우 트리를 구성하고, 탐색하는 과정이 극단적으로 늘어날 수 있는데
이 경우 트리를 구성후 다시 탐색하며 postorder로 출력하면 시간초과가 발생하도록 문제를 설계했다는 판단하에 두번째 풀이가 정답이라 생각했다.

---