백준 2263번 트리의 순회

서론

2263번: 트리의 순회

이 문제를 풀면서 느낀 게 많아서 기록으로 남기려고 합니다. 시간제한이나 공간 제한에 있어서 다시 한번 생각해볼 수 있는 문제였습니다.

제한 조건

• 시간제한 - 5초

시간제한은 5초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 이번 문제는 수없이 많은 recursion을 사용하기 때문에 recursion을 하기 전 너무 많은 코스트를 사용하면 안 됩니다. 처음에 recursion을 하기 전 inorder에서 root을 찾을 때 n만큼의 탐색을 사용했는데 이게 recursion 횟수만큼 곱해져서 시간초과가 났었습니다. 이 부분을 수정하여 시간초과를 통과했습니다.

• 메모리 제한 - 128MB

메모리 제한은 128MB입니다. 앞선 문제들에서 말했다시피 대부분 문제가 주어진 정보를 선언하는 데는 문제가 없습니다. inorder와 postorder를 선언하기엔 충분한 크기입니다.
이 문제에서는 recursion을 사용하는데 recursion을 할 때 인자로 list를 주면 안 됩니다. 함수가 호출될 때마다 인자를 복사해서 사용하기 때문에 recursion이 수없이 많이 일어나면 무수한 양의 list를 저장해야 하므로 메모리 초과가 나옵니다. 따라서 list는 한 개만 두고 index를 넘김으로써 list의 값을 사용해야 합니다.

트리의 순회

문제에서 postorder와 inorder를 줍니다. postorder의 가장 마지막 값은 트리의 root과 되고 inorder에서 root을 기준으로 left tree와 right tree를 구할 수 있습니다. root, left, right를 모두 알기 때문에 graph를 다시 만들 필요 없이 순서를 재조합하여 preorder를 구할 수 있습니다. 각 left, right tree에서도 post order를 통해 root, in order를 통해 left, right를 똑같은 방법을 통해 구할 수 있기 때문에 recursion을 사용하여 쉽게 풀 수 있습니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
roots = [0] * (n+1)


def preorder(posts, poste, ins, ine):

    if posts > poste or ins > ine:
        return

    root = postorder[poste]

    root_idx = roots[root]
    print(root, end=' ')
    # left
    preorder(posts, posts+(root_idx-ins)-1, ins, root_idx-1)
    # right
    preorder(posts+(root_idx-ins), poste-1, root_idx+1, ine)

# 이 부분이 시간을 단축하는 핵심입니다.
for i in range(n):
    roots[inorder[i]] = i

preorder(0, n-1, 0, n-1)

생각

이 문제를 풀면서 크게 배운 점은 두 가지입니다.

1. 처음 주어진 list의 부분집합을 사용하며 문제를 풀 때 함수에 부분집합 자체를 넘겨주면 안 됩니다. 함수가 호출될 때 인자를 복사해서 사용하기 때문에 쓸모없는 메모리를 엄청나게 잡아먹습니다. index를 넘겨줌으로써 list의 값을 사용해야 합니다.
2. list의 인덱스만 넘어가기 때문에 전체 list를 사용하여 계산해야 하는 부분은 함수 바깥에서 할 수 있습니다. 처음에 inorder에서 left와 right를 구별하기 위해 root을 찾을 때 아래와 1번과 같은 방법을 사용했습니다. 하지만 이렇게 하면 모든 recursion에서 최악의 경우 n이 곱해지기 때문에 시간초과가 납니다. 따라서 root_idx는 함수 바깥에서 한 번만 n번 탐색하여 구하는 방법을 2번처럼 사용해야 합니다.

   # 1번
   for i in range(ins, ine+1):
        if root == inorder[i]:
            root_idx = i
            break
   # 2번
   for i in range(n):
    roots[inorder[i]] = i
   

   이런 부분들은 구현 자체는 쉽지만 사실 생각해내는 게 너무 어려웠을 것 같습니다. 이런 센스들을 한 개씩 배워나가야겠습니다.