트리 복구 (6597번) - 백준 (BOJ)

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

6597번: 트리 복구

 

백준 - 트리 복구 (Tree Recovery) (6597번)

 

난이도 : Gold 3

알고리즘 : DFS on Tree

풀이 소요 시간 : 30 mins

 

import sys


def get_posto(preo, ino):
    if len(preo) <= 1:
        return preo
    k_i = ino.index(preo[0])
    return get_posto(preo[1:k_i+1], ino[:k_i]) + get_posto(preo[k_i+1:], ino[k_i+1:]) + preo[0]


if __name__ == '__main__':
    for query in sys.stdin.readlines():
        print(get_posto(*query.split()))

 

이진 트리 (binary tree) 의 전위 순회 (Preorder) 와 중위 순회 (Inorder) 가 주어졌을 때,

후위 순회 (Postorder) 를 구하는 문제이다.

 

전위 순회 문자열의 첫 번째 문자를, 중위 순회 안에서 찾고

그 기준으로 중위 순회 문자열을, 왼쪽 문자열과 오른쪽 문자열로 나눠서

각 문자열에 대해 다시 똑같은 작업을 반복하면 된다.

 

그리고 return할 때는, 후위 순위를 출력하는 것이 목표이기 때문에

(왼쪽 문자열) + (오른쪽 문자열) + (전위 순회 첫 번째 문자)

이 순서로 return 하면 된다.

 

DBACEGF
ABCDEFG

BAC EGF D
ABC EFG D

A C B  GF E  D
A C B  FG E  D

A C B F G E D

 

 

---

 

옛날에 비슷한 문제를 푼 경험이 있어서,

재귀를 활용해 어렵지 않게 풀 수 있었다.