[Python]트리 백준 2263

   문제

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

답을 구하는 방법이 바로 떠오르지 않는다.

트리를 그려보고 전위 중위 후위순회를 각각 구하고 비교해 봐야겠다.

먼저 이전 문제애 사용던 코드를 활용해 각각의 전위 중위 후위순회를 구해보았다.

A B C

B . F

C D E

D . .

E . .

F G H

G . .

H . .

ABFGHCDE

BGFHADCE

GHFBDECA

후위순회는 마지막 노드가 루트이다.

중위순회는 부모노드를 기준으로 나눌수 있다.

먼저 후위순회 부모노드를 구하고 중위순회를 통해 나눈것을 반복하면 트리를 구할수

있다.

BGFH A DCE

GHFB DEC A

A

BGFH        DCE

먼저 이렇게 나누고 나면

후위순회의 나누어진 그룹의 가장 오른쪽 노드들은 부모노드가 된다.

다시 BC를 부모노드로 나눠보자

B GFH / A / D C E 

GHF B / DE C / A

A

B                    C

GHF        D        E

이제 F와 E를 부모노드로 다시나누자

B/ G F H / A / DCE

GH F /B / D E /C / A

A

B                  C

F        D        E

G       H

이렇게 트리를 완성할 수 있다.

이제 코드로 구현해보자

바로 전위순회로 구할수도 있지만 사실 트리를 구하는게 중요하다고 생각하여

트리를 구하고 다시 전위순회를 구하는 방식으로 구현해 봐야겠다.

import sys
sys.setrecursionlimit(10**9)
 
n = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))#중위순회
postorder = list(map(int, sys.stdin.readline().split()))#후위순회
in_location=[0 for _ in range(n+1)]#인자를 찾을때 한번에 찾기위해서
for i in range(n):
    in_location[inorder[i]]=i
 
tree=[[0,0] for _ in range(n+1)]#트리저장
 
def find_tree(in_l,in_r,post_l,post_r): #중위순회 범위 후위순회 범위
    if post_l <= post_r:
        parents=postorder[post_r]#후위순회에서 부모노드 찾기
        p_index=in_location[parents]
        # for i in range(in_l,in_r+1):#인자찾기
        #     if inorder[i]==parents:
        #         p_index=i
 
        l_count=p_index-in_l#왼쪽인자 갯수
        if l_count>0:#트리에 왼쪽자식노드 추가
            tree[parents][0]=postorder[post_l+l_count-1]
        r_count=in_r-p_index#오른쪽인자 갯수
        if r_count>0:#트리에 왼쪽자식노드 추가
            tree[parents][1]=postorder[post_r-1]
 
 
        find_tree(in_l , p_index-1 , post_l , post_l+l_count-1)#부모노드를 기준으로 왼쪽노드
        find_tree(p_index+1 , in_r , post_r-r_count , post_r-1)#부모노드 기준 오른쪽
 
find_tree(0,n-1,0,n-1)
# print(tree)
 
def pre_order(start):
    print(start,end=" ")
    if tree[start][0] != 0:
        pre_order(tree[start][0])
    if tree[start][1] != 0:
        pre_order(tree[start][1])
 
pre_order(postorder[-1])

문제를 푸는과정에서 런타임에러와 시간초과를 만났다.

런타임에러의 경우 재귀의 깊이로 인한 문제였고

sys.setrecursionlimit(10**9)로 재귀의 깊이를 설정하였다.

그 뒤 시간초과가 났는데 후위순회에서 찾은 부모노드를 중위순회에서 찾는과정에서

 O(n^2)의 시간을 소요하도록 구하였다.

이 과정을 

n_location=[0 for _ in range(n+1)]#인자를 찾을때 한번에 찾기위해서

for i in range(n):

    in_location[inorder[i]]=i

처음에 이 과정을 통해 각 인자에 대응하는 순서를 모두 구해 O(n)으로 줄였더니 통과

할수 있었다.문제에서 원하는것은 트리가 아닌 전위순회를 구하는것이므로 굳이 트리

를 구해서 풀 필요는없다.

아래 코드는 전위순회만 구하는 코드이다.

import sys
sys.setrecursionlimit(10**9)
 
n = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))#중위순회
postorder = list(map(int, sys.stdin.readline().split()))#후위순회
in_location=[0 for _ in range(n+1)]#인자를 찾을때 한번에 찾기위해서
for i in range(n):
    in_location[inorder[i]]=i
 
 
def pre_order(in_l,in_r,post_l,post_r): #중위순회 범위 후위순회 범위
    if post_l <= post_r:
        parents=postorder[post_r]#후위순회에서 부모노드 찾기
 
        print(parents,end=" ")
        p_index=in_location[parents]
        # p_index = 0  # 중위순회의 부모노드 위치
        # for i in range(in_l,in_r+1):#인자찾기
        #     if inorder[i]==parents:
        #         p_index=i
        #         break
        l_count=p_index-in_l#왼쪽인자 갯수
        r_count=in_r-p_index#오른쪽인자 갯수
 
        pre_order(in_l , in_l+l_count-1 , post_l , post_l+l_count-1)#부모노드를 기준으로 왼쪽노드
        pre_order(in_r-r_count+1 , in_r , post_r-r_count , post_r-1)#부모노드 기준 오른쪽
 
pre_order(0,n-1,0,n-1)