문제
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
출력
첫째 줄에 프리오더를 출력한다.
해설
해당 문제는 주어진 인오더(중위 순회)와 포스트오더(후위 순회)를 사용해 프리오더(전위 순회)를 구하는 문제이다.
먼저, 각 순회의 특징을 알아야 한다.
전위 순회 : (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회 : (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회 : (왼쪽 자식) (오른쪽 자식) (루트)
여기서 발견할 수 있는 사실은 후위 순회를 통해 루트 노드를 찾을 수 있고, 이 루트 노드를 활용해 중위 순회에서 왼쪽 자식들과 오른쪽 자식들을 나눌 수 있다는 것이다.
7
4 2 1 5 3 6 7
4 2 5 7 6 3 1위와 같은 입력이 들어왔다고 가정해보자.
첫 번째 줄은 노드 개수 N을
두 번째 줄은 중위 순회 결과를
세 번째 줄은 후위 순회 결과를 나타내고 있다.
후위 순회 가장 마지막 노드(1)가 루트 노드이므로 중위 순회 결과에서 1을 찾는다.
인덱스 번호가 1번부터 n번까지라고 가정한다면, 1은 중위 순회 결과에서 3번 인덱스임을 알 수 있다. 그렇다면 중위 순회 결과에서 1~2번 인덱스는 왼쪽 자식들, 4~7번 인덱스는 오른쪽 자식들이 된다.
그렇다면 후위 순회 결과는 어떻게 나누어질까?
중위 순회의 왼쪽 자식들의 개수는 2개, 오른쪽 자식들의 개수는 4개이다. 이걸 후위 순회 결과에 적용하여 Start 지점으로부터 중위 순회의 왼쪽 자식들 개수만큼의 범위와 왼쪽 자식들을 제외하고 가장 마지막 노드인 루트 노드를 제외한 범위를 나누어 주면 된다.
이젠 하위 트리로 나누어진 중위 순회의 4~7번(5 3 6 7)과 후위 순회의 3~6번(5 7 6 3)을 가지고 위의 순서를 반복해주면 된다. 즉, 후위 순회의 마지막 노드(3)를 중위 순회에서 찾고 나누어주고를 반복하면 된다.
이때 중요한 부분은 구하고자 하는 전위 순회의 특징이다. 전위 순회는 (루트) (왼쪽 자식) (오른쪽 자식) 순서로 탐색하므로 루트 결과인 마지막 노드를 저장한 후 재귀를 이용해 왼쪽, 오른쪽 순서대로 탐색해주는 것이 중요하다.
풀이
import java.util.*;
import java.io.*;
public class Main {
static int[] inorder, postorder, preorder;
static int n, index;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
inorder = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < n; i++) {
inorder[i] = Integer.parseInt(st.nextToken());
}
postorder = new int[n];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < n; i++) {
postorder[i] = Integer.parseInt(st.nextToken());
}
preorder = new int[n];
index = 0;
getPreOrder(0, n - 1, 0, n - 1);
StringBuilder sb = new StringBuilder();
for(int num :preorder) {
sb.append(num).append(" ");
}
System.out.println(sb.toString());
}
public static void getPreOrder(int is, int ie, int ps, int pe) {
if (is <= ie && ps <= pe) {
preorder[index++] = postorder[pe];
int i;
for (i = is; i <= ie; i++) {
if (inorder[i] == postorder[pe]) {
break;
}
}
// 왼쪽
getPreOrder(is, i - 1, ps, ps + (i - 1) - is);
// 오른쪽
getPreOrder(i + 1, ie, ps + i - is, pe - 1);
}
}
}위의 풀이는 시간이 오래걸린다. getPreOrder() 메서드를 보면 중위 순회의 결과에서 후위 순회 마지막 노드에 해당하는 값을 찾는 과정이 시간을 많이 잡아먹기 때문이다.
이 부분을 해결하기 위해 temp 배열을 만들어 중위 순회 결과에 해당하는 노드 값을 인덱스로하여 인덱스 값을 저장해주었다. 즉, 4번 노드가 1번 인덱스에 저장되어 있다면 temp 배열의 4번 인덱스에 1번(인덱스)를 저장한다.
import java.io.*;
import java.util.*;
public class Main {
static int[] inorder, postorder, preorder, temp;
static int n, index;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
inorder = new int[n + 1];
temp = new int[n + 1];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= n; i++) {
inorder[i] = Integer.parseInt(st.nextToken());
temp[inorder[i]] = i;
}
postorder = new int[n + 1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= n; i++) {
postorder[i] = Integer.parseInt(st.nextToken());
}
preorder = new int[n + 1];
index = 1;
getPreOrder(1, n, 1, n);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
sb.append(preorder[i]).append(" ");
}
System.out.println(sb.toString());
}
public static void getPreOrder(int is, int ie, int ps, int pe) {
if (is <= ie && ps <= pe) {
preorder[index++] = postorder[pe];
int i = temp[postorder[pe]];
// 왼쪽
getPreOrder(is, i - 1, ps, ps + (i - 1) - is);
// 오른쪽
getPreOrder(i + 1, ie, ps + i - is, pe - 1);
}
}
}
