백준 2263 트리의 순회

failed

답

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

n = int(input().rstrip())
inorder = list(map(int, input().rstrip().split()))
postorder = list(map(int, input().rstrip().split()))
index = [0] * (n + 1) #후위 순회의 마지막 노드를 기준으로 -> 중위순회 왼 / 오 알기 위한 인덱스 값 저장
for i in range(n):
    index[inorder[i]] = i
preorder = []

def order(i_s, i_e, p_s, p_e):
    if (i_s > i_e) or (p_s > p_e): return
    root = postorder[p_e]
    preorder.append(root)
    left = index[root] - i_s #왼쪽 서브트리 개수
    right = i_e - index[root] #오른쪽 서브트리 개수
    order(i_s, i_s + left - 1, p_s, p_s + left - 1)  # 쪽 서브트리
    order(i_e - right + 1, i_e, p_e - right, p_e - 1)  # 오른쪽 서브트리

order(0, n - 1, 0, n - 1)
print(*preorder, sep=' ')

아이디어를 알아도 재귀하는 방법을 모르겠어서 결국 검색을...
분할 정복 문제였고, 어..려..웠..다...
recursion limit을 10 ** 4로 하면 recursion error가 뜨고, 10 ** 6으로 하면 메모리가 초과된다.
딱 10 ** 5로 해야하는게 웃음벨.. 백준은 참 묘하다