백준 2263번 트리의 순회

정보

문제 바로가기 [클릭]

난이도: Gold2

관련 개념: #트리 #분할정복 #재귀

---

조건

시간 제한	메모리 제한
5 초	128 MB

---

문제

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

---

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

---

출력

첫째 줄에 프리오더를 출력한다.

---

예제 입출력 1

입력

3
1 2 3
1 3 2

출력

2 1 3

---

코드(파이썬)

import sys


sys.setrecursionlimit(100001)

def check(in_start, in_end, post_start, post_end):
    global result
    
    root_value = postorder[post_end]
    l_length = inorder.index(root_value) - in_start
    result.append(root_value)
    
    if l_length > 1:
        check(in_start, in_start+l_length-1, post_start, post_start+l_length-1)
    elif l_length == 1:
        result.append(inorder[in_start])
        
    if in_start+l_length+1 < in_end:
        check(in_start+l_length+1, in_end, post_start+l_length, post_end-1)
    elif in_start+l_length+1 == in_end:
        result.append(inorder[in_end])
    
n = int(sys.stdin.readline())
inorder = sys.stdin.readline().split()
postorder = sys.stdin.readline().split()
result = []

check(0, n-1, 0, n-1)
print(*result)

---

특이사항

• 분할정복을 위해 구역을 나눠서 해결하는 것은 맞음
• 도저히 그 다음 아이디어가 생각나지 않아 pypy로 제출 후 풀이 확인
• 내 코드(331,124KB, 15,084ms)에 비해 우수한 코드(바로가기, 161,052KB, 332ms)와 비교

  • from sys import stdin, setrecursionlimit
    setrecursionlimit(10 ** 9)
    
    n = int(stdin.readline())
    
    inorder = list(map(int, stdin.readline().split()))
    postorder = list(map(int, stdin.readline().split()))
    
    inorder_index = [0] * (n + 1)
    for i in range(n):
        inorder_index[inorder[i]] = i
    
    answer = []
    def preorder(in_start, in_end, post_start, post_end):
        if (in_start > in_end) or (post_start > post_end): return
    
        parent = postorder[post_end]
        answer.append(parent)
    
        left = inorder_index[parent] - in_start
        right = in_end - inorder_index[parent]
    
        preorder(in_start, in_start + left - 1, post_start, post_start + left - 1)
        preorder(in_end - right + 1, in_end, post_end - right, post_end - 1)
    
    preorder(0, n - 1, 0, n - 1)
    print(*answer)
    

  • 인덱스 확인
    • 기존: index 메서드 이용
    • 개선: inorder_index 리스트를 생성해 inorder 인덱스 확인을 O(1)에 해결

---

참고문헌

-