백준 5639번 이진 검색 트리

서론

5639번: 이진 검색 트리

트리의 순회 문제입니다. 순회 결과가 먼저 주어지고 다시 그래프를 만드는 개념도 어려웠고, 그래프를 만든 후에도 시간초과가 나서 그래프를 만들지 않고 바로 후위순회를 해야 해서 어려웠습니다.

제한 조건

• 시간제한 - 1초

시간제한은 1초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 처음에는 preorder를 기반으로 graph를 다시 만들고 그 graph를 postorder 해서 풀었는데 시간 초과가 났고 graph를 만들지 않고 바로 postorder를 print 하는 방법으로 바꿔서 풀었습니다.

• 메모리 제한 - 256MB

메모리 제한은 256MB입니다. 앞선 문제들에서 말했다시피 대부분 문제가 주어진 정보를 선언하는 데는 문제가 없습니다.

트리의 순회

트리의 순회는 아래와 같은 특성을 가집니다.

1. 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 노드의 키보다 작다.
2. 노드의 오른쪽 서브 트리에 있는 모든 노드의 키는 노드의 키보다 크다.
3. 왼쪽, 오른쪽 서브 트리도 트리의 순회이다.

이런 특성 때문에 트리의 순회는 어떠한 order가 주어졌을 때 바로 root, left, right tree를 구할 수 있고 tree를 다시 만들지 않아도 순서를 재조합하여 탐색 order를 바꿀 수 있습니다.
설명하자면 root 다음 root보다 작은 숫자가 나오는 부분은 left가 되고 큰 숫자가 나오는 부분은 right가 됩니다. 이렇게 되면 이미 left, right, root을 모두 알 수 있으므로 pre, in, post order를 모두 바로 사용할 수 있습니다.

import sys
from collections import deque as dq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

# 입력에 대한 길이가 없기 때문에 EOF를 받을 때까지 입력을 받는다.
preorder = []
while True:
    try:
        preorder.append(int(input()))
    except:
        break


def post_order(start, end):
    if start > end:
        return
    idx = end+1
    # 처음으로 큰 값이 나오는데 찾는데 시간복잡도 O(n)
    for i in range(start+1, end+1):
        if preorder[start] < preorder[i]:
            idx = i
            break
    
    # 두개로 나눠서 계속 호출하기 때문에 시간복잡도 O(logn)
    post_order(start+1, idx-1)
    post_order(idx, end)
    print(preorder[start])

    # 결과적으로 nlogn의 시간복잡도를 가지고 시간문제를 통과 할 수 있습니다.

post_order(0, len(preorder)-1)

생각

그런데 처음에 graph를 만들어서 postorder로 다시 탐색하는 코드도 계산상은 시간복잡도가 통과할 것 같은데 통과를 하지 못합니다. 아래 코드의 주석을 보면 결론적으로 graph를 다시 그리더라도 시간복잡도가 O(nlogn)로 통과해야 할 것 같은데 통과를 못 합니다. 정확히 알 순 없지만 코드에 조건들이 많아지면서 O(1)의 시간복잡도를 가지는 애들이 조금은 커져서 그런 게 아닐까 싶습니다.

그리고 이 문제 때문에 찾아보면서 알게 된 건데 사전의 key 값으로 dict[key]를 접근하는 게 O(1)이라고 합니다. 신기하네요. key를 어떤 식으로 저장하길래 O(1)일까요…?

import sys
from collections import deque as dq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


# 트리순회는 별다른 조건없이 모든 노드를 다 순회하므로 시간복잡도 N이다.
def postorder(chr):
    if graph[chr][0] != '.':
        postorder(graph[chr][0])
    if graph[chr][1] != '.':
        postorder(graph[chr][1])
    print(chr)


# 입력에 대한 길이가 없기 때문에 EOF를 받을 때까지 입력을 받는다.
preorder = []
while True:
    try:
        preorder.append(int(input()))
    except:
        break
graph = {}
for parent in preorder:
    graph[parent] = []

start = 0
end = len(preorder)-1


# 총 시간복잡도 NlogN
def make_tree(start, end):
    parent = preorder[start]
    idx = end
    left = -1
    right = -1
    # parent보다 커지는곳을 찾는 부분의 시간복잡도 N
    while idx > -1 and idx >= start:
        if preorder[idx] < parent:
            left = idx
        if preorder[idx] > parent:
            right = idx
        idx -= 1

    # 하위 left, right트리를 나누는 부분이 logN
    if left == -1 and right == -1:
        graph[parent].append('.')
        graph[parent].append('.')
    elif left == -1:
        graph[parent].append('.')
        graph[parent].append(preorder[right])
        make_tree(right, end)
    elif right == -1:
        graph[parent].append(preorder[left])
        graph[parent].append('.')
        make_tree(left, end)
    else:
        graph[parent].append(preorder[left])
        graph[parent].append(preorder[right])
        make_tree(left, right-1)
        make_tree(right, end)


make_tree(start, end)
# print(graph)

postorder(preorder[0])

# 이렇게 하게 되면 총 시간복잡도 NlogN + N하게 되어 O(NlogN)인데 시간초과가 나옵니다.