오늘의 한 마디
포스트오더와 인오더로 프리오더를 구할 수 있다니?!

• Baekjoon 문제 링크
• 현재 백준 문제집: 단기간 성장을 풀고 있습니다.

문제

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

입력

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

출력

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

예제 입력 1

3
1 2 3
1 3 2

예제 출력 1

2 1 3

---

발상

프리오더, 인오더, 포스트오더

현재 노드, 왼쪽/오른쪽 자식 노드를 대상으로 하며,
현재 노드를 몇 번째로 방문하는지가 기준이다.

• 프리오더(preorder; 전위 순회) : 현재 노드 -> 왼쪽 자식 -> 오른쪽 자식
• 인오더(inorder; 중위 순회) : 왼쪽 자식 -> 현재 노드 -> 오른쪽 자식
• 포스트오더(postorder; 후위 순회) : 왼쪽 자식 -> 오른쪽 자식 -> 현재 노드

해설

어떻게 인오더와 포스트오더 정보를 가지고 프리오더를 구할 수 있을까?

뭔가 구할 수 있을 것 같아서 예시 트리를 만들어서 이것저것해봤는데,
규칙도 잘 안 보이고 한꺼번에 고려할 게 너무 많은 기분이었다.

해설 링크에 있는 그림을 가져와봤다.
뭔가 정리되는 기분이 들지 않는가?

포스트오더에서 얻을 수 있는 가장 핵심 정보는, 루트 노드다!

인오더에서는 루트 노드가 가운데 숨겨져 있어 무엇이 루트 노드인지 알 수 없지만, 포스트오더는 왼쪽 자식 -> 오른쪽 자식 -> 현재 노드 순으로 순회하기 때문에 전체 트리의 마지막 요소는 루트 노드다.

---

풀이 순서는 다음과 같다.

1. 포스트오더의 가장 마지막 요소를 찾는다. 그게 바로 루트 노드다.

    parent = postorder[post_end] 

2. 인오더에서 루트 노드가 어느 인덱스에 위치하는지 찾는다.

inorder.index(parent)

3. 인오더에서 루트 노드 왼쪽은 왼쪽 트리의 개수고, 오른쪽은 오른쪽 트리의 개수다.

    left = inorder.index(parent) - in_start
    right = in_end - inorder.index(parent)

4. 포스트오더에도 왼쪽 트리의 개수, 오른쪽 트리의 개수 만큼을 나눈다.

    dc(in_start, in_start+left-1, post_start, post_start+left-1)
    dc(in_end-right+1, in_end, post_end-right, post_end-1)

그렇게 생긴 왼쪽 트리, 오른쪽 트리에 대해서
다시 1~4 단계를 재귀적으로 적용하여 분할 정복(Divide & Conquer)으로 문제를 해결한다.

---

풀이

import sys
sys.setrecursionlimit(100000)

n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
preorder = []

def dc(in_start, in_end, post_start, post_end): # dc = divide & conquer
    if in_end < in_start or post_end < post_start:
        return

    parent = postorder[post_end] # 후위 순회의 마지막 원소는 해당 트리의 부모다. 
    preorder.append(parent) # 전위 순회는 부모 -> 왼쪽 -> 오른쪽 순으로 순회하므로
    left = inorder.index(parent) - in_start
    right = in_end - inorder.index(parent)
    
    # 위 링크의 그림을 보면 inorder와 postorder 둘다 왼쪽은 범위가 같은데, 오른쪽은 다름. 
    # in_end-right+1 ~ in_end vs post_end-right ~ post_end-1
    dc(in_start, in_start+left-1, post_start, post_start+left-1)
    dc(in_end-right+1, in_end, post_end-right, post_end-1)

dc(0, n-1, 0, n-1)
print(*preorder)

이제까지 print(' '.join(map(str, preorder)))라고 써서 출력했는데,
그냥 print(*preorder)를 해도 똑같이 나온다! 역시 파이썬 짱
default는 sep=' '이고, sep 변수 값을 변경하여 사이에 들어갈 문자열을 지정할 수 있다. .