문제
이진트리는 컴퓨터 과학에서 아주 중요한 역할을 해 왔다.
많은 알고리즘이 이진트리를 이용하고 있으며, 이진트리의 또 다른 이용 역시 지금도 꾸준히 연구되고 있다.
이진트리를 순회하는 방법은 루트를 언제 출력하느냐에 따라 크게 세 가지로 나눌 수 있다.
첫 번째는 preorder 순회법으로,
트리의 루트를 먼저 출력한 뒤 재귀적으로 왼쪽 부트리와 오른쪽 부트리를 차례로 순회하는 방법이다.
두 번째는 inorder 순회법으로, 왼쪽 부트리를 순회한 뒤 루트를 출력하고, 그 다음에 오른쪽 부트리를 순회한다.
마지막 방법은 postorder 순회법으로, 왼쪽 부트리와 오른쪽 부트리를 먼저 순회하고 난 뒤 루트를 출력하는 것이다.
예를 들어, 아래의 이진트리를 위에서 설명한 세 가지 방법에 따라 순회하면 다음과 같은 결과를 얻을 수 있다.
트리를 preorder로 순회한 순서와 inorder로 순회한 순서가 주어지면,
그에 해당하는 이진트리를 만들어 내는 것이 가능하고, 조건을 만족하는 이진트리는 단 하나만 존재함이 알려져 있다. Preorder 순회 결과와 inorder 순회 결과를 바탕으로 postorder 순회 결과를 출력하자.
입력
입력의 첫 번째 줄에 트리를 preorder로 순회한 순서가 주어지고,
두 번째 줄에는 inorder로 순회한 순서가 주어진다. 순회 결과는 공백 없는 문자열로 주어질 것이다.
문자열은 대문자만으로 이루어져 있기 때문에, 트리의 정점 개수는 많아야 26개이다.
입력 데이터는 항상 옳다고 가정한다(규칙에 어긋나는 입력은 들어오지 않는다).
출력
예제
DBACEGF
ABCDEFG
ACBFGED
로그인해야 코드를 작성할 수 있어요.