(Python) - BOJ(2263번) : 트리의 순회

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

2263번: 트리의 순회

---

• 문제 : 

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

재귀를 이용한 분할정복 문제였습니다.

 

이진트리의 pre, in, post order의 개념을 알고 있어야 풀 수 있는 문제였습니다. 

아이디어는 다음과 같습니다.

 

1. postorder와 inorder가 주어질 때, postorder의 가장 오른쪽 원소는 그 subtree의 root입니다. 

 

2. preorder는 가장 상위 tree의 root부터 좌, 우 subtree의 root를 출력하는 형태로 진행하므로 이 root를 answer 배열에 넣어줍니다. 

 

3. 이 root 값을 inorder 배열에서 찾는다면 찾은 인덱스를 기준으로 왼쪽과 오른쪽 subtree로 나눌 수 있습니다.

 

4. 왼쪽과 오른쪽 subtree를 postorder 배열에서 나누어준 후 1번으로 되돌아가 post의 가장 오른쪽 원소를 root로 설정하는 것부터 진행합니다.

 

 

재귀의 종료시점은 왼쪽, 또는 오른쪽 서브트리의 길이가 0보다 작아지는 시점입니다.

 

추가 : 

첫 번째 런타임 에러는 처음에 테스트용으로 재귀 횟수를 maximum 100으로 지정해두어서 생긴 문제입니다.

두 번째로, 시간 초과를 생각하지 못했는데 postorder 배열에서 찾은 root를 inorder 배열에서 찾을 때

index() 메소드를 사용했습니다. 이 메소드의 시간복잡도는 O(N)으로 매 분할마다 실행한다면 최대 O(N^2logN)으로 N의 최댓값이 100,000인 이 문제에서는 당연히 시간초과가 발생하게 됩니다. 

이 문제를 해결하기 위해 inorder의 각 요소의 index를 미리 저장하는 index라는 배열을 만들어 O(1)의 시간복잡도로 root의 index를 찾을 수 있도록 하였습니다.

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))
answer = []
index = [0] * (N+1)
for i in range(N):
    index[inorder[i]] = i

def preorder(s1,e1,s2,e2):
    if s1 > e1 or s2 > e2:
        return
    root = postorder[e2]
    rootIdx = index[root]
    answer.append(root)
    leftLength = rootIdx-s1
    preorder(s1, rootIdx-1, s2, s2 + leftLength - 1)
    preorder(rootIdx+1, e1, s2 + leftLength , e2-1)
preorder(0,N-1,0,N-1)
print(' '.join(list(map(str,answer))))