[BOJ][Python]5639 풀이

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

5639번: 이진 검색 트리

import sys
ssr = sys.stdin.readline
sys.setrecursionlimit(100000)

def make_tree():
    first_key = int(ssr())
    tree = {first_key:[0, 0]}
    while True:
        try:
            cur_key = int(ssr())
            tree[cur_key] = [0, 0]
            parent_key = first_key
            while True:
                if cur_key < parent_key: # 부모보다 작으면
                    if tree[parent_key][0] == 0: # 왼쪽 비어있으면
                        tree[parent_key][0] = cur_key
                        break
                    else: # 왼쪽 안 비어 있으면
                        parent_key = tree[parent_key][0] # 키 왼쪽 아래로 이동
                else: # 부모보다 크면
                    if tree[parent_key][1] == 0: # 오른쪽 비어 있으면
                        tree[parent_key][1] = cur_key
                        break
                    else: # 오른쪽 안 비어있으면
                        parent_key = tree[parent_key][1] # 오른쪽 아래로 이동
        except:
            return first_key, tree

def postorder(n):
    if n == 0:
        return
    else:
        postorder(tree[n][0])
        postorder(tree[n][1])
        print(n)
        return
    
start, tree = make_tree()
postorder(start)

이번 문제는 뭔가 정신을 놓고 있었던 것 같습니다. 이유는 모르겠는데 하루종일 이걸 거꾸로 타고 올라가서 판단을 하는 방식으로 코드를 짜고 있었어요. 이진 탐색 트리를 생각할 때는 제대로 위에서부터 비교해가면서 내려왔었는데 코드 구현은 거꾸로 하고 있으니 시간만 계속 날리고 구현은 힘들고... 좀 전에 멍청한 짓을 깨닫고 구현하는데에는 5분도 안걸린 것 같네요. 아직도 얼떨떨합니다.

 

구현은 그냥 전위 순회의 결과를 하나씩 받아가면서 현재 위치의 값보다 작으면 왼쪽, 크면 오른쪽으로 보내고 해당 노드가 비어있다면 추가하고 아니라면 비어있는 노드가 나올 때까지 해당 과정을 반복합니다. 그냥 이진 탐색 트리를 만드는 기본적인 코드입니다.

 

후위 순회는 왼쪽 - 오른쪽 - 부모 순으로 출력하는 것이기 때문에 재귀로 짜서 자식 노드가 없으면 자기 자신을 출력하도록 하면 됩니다.

 

다만 해당 방법은 런타임이 상당히 안좋습니다. 그래서 빠른 실행 시간을 갖는 분들의 코드를 좀 확인해봤더니 전위 순회의 결과만 가지고도 그걸 후위 순회로 바로 바꾸는 방법을 사용하더라구요. 노드 갯수 같은게 따로 안주어질 때도 뭔가 쉽게 하는 방법이 있나보다 생각만 했었는데 역시 있었네요.

 

첫번째는 굳이 트리를 만들지 않고 주어진 입력만 사용하는 방법입니다. postorder 함수는 배열을 받아서 배열의 첫 원소를 부모로 하고(이건 전위순회니까 당연하죠) 다른 원소와 첫 원소의 크기를 비교해서 왼쪽 오른쪽으로 나눈 다음에 왼쪽과 오른쪽으로 나눠진 배열에 대해서 postorder를 재귀 호출하는 방법입니다.

 

이진 탐색 트리의 특성상 부모 보다 왼쪽에 있는 값들은 전부 작다는 보장이 되기 때문에 이런 방법이 사용가능하네요. 다만 구현만 간단해졌을 뿐이고 런타임에서 딱히 이득이 있진 않습니다. 조금씩 비교해야하는 배열 사이즈가 줄어들긴 하지만 원소가 하나가 될 때 까지 이미 비교했던 원소를 계속해서 비교하고 리스트에 추가하는 과정을 거쳐야 하므로 O(n^2)의 시간복잡도를 갖겠네요.

import sys
ssr = sys.stdin.readline
sys.setrecursionlimit(10000)

def postorder(tree):
    if len(tree) == 0:
        return
    else:
        parent = tree[0]
        left = []
        right = []
        for i in range(1, len(tree)):
            if parent > tree[i]:
                left.append(tree[i])
            else:
                right.append(tree[i])
        postorder(left)
        postorder(right)
        print(parent)
        
nodes = []
while True:
    try:
        nodes.append(int(ssr()))
    except:
        break
postorder(nodes)

두번째는 중복계산을 조금 줄이는 코드입니다. 사실 1등 분의 런타임에는 한참 못미치긴 합니다만, 아직 그 분의 코드를 완벽하게 이해하지는 못해서 이번에는 첨부하지 않으려 합니다. 코드를 못알아보겠는 건 아닌데 그 분이 어떤 생각을 갖고 그렇게 작성을 했는지가 잘 파악이 안되네요.

 

제가 위에서 조금 더 고친 버전인 아래 코드는 모든 원소를 다 비교하고 나눠서 재귀 호출을 하는게 아니라 선형탐색을 하다가 부모보다 큰 값이 나오면 해당 인덱스를 기준으로 나눠서 재귀 호출을 하는 방식입니다. 항상 인덱스가 절반이라고 가정하면 연산량은 n*n/2가 되겠네요. 아주 약간 줄어들었습니다.

 

이렇게 전부 비교를 하지 않고 큰 값이 나왔다고 반복문을 종료할 수 있는 이유는 뭘까요? 정답은 해당 입력이 전위 순회의 결과이고 해당 트리가 이진 탐색 트리이기 때문입니다. 전위 순회는 부모 - 왼 - 오른 순으로 방문을 하죠. 그래서 맨 처음 원소는 트리의 루트 노드라고 볼 수 있고 루트 노드보다 큰 값이 나왔다면 그건 오른쪽 원소니까 모든 값을 비교하지 않아도 오른쪽 왼쪽을 나눌 수 있는 겁니다. 아마 이 부분을 이용해서 좀 더 런타임 개선을 할 수 있을 것 같은데 다음에 완벽히 이해가 되면 그 때 추가 코드를 올려보도록 하겠습니다.

import sys
ssr = sys.stdin.readline
sys.setrecursionlimit(10002)

def postorder(start, end):
    if start >= end:
        return
    mid = start+1
    for i in range(start+1, end):
        if preorder[start] < preorder[i]:
            mid = i
            break
    postorder(start+1, mid)
    postorder(mid, end)
    print(preorder[start])
        
preorder = []
while True:
    try:
        preorder.append(int(ssr()))          
    except:
        break
postorder(0, len(preorder))

이렇게 풀어놓고 보니까 아래에서 제시한 풀이는 분할정복같 느낌이 드네요.