[BOJ] 백준 6597번 트리 복구 (Java)

#6597 트리 복구

난이도 : 골드 3

유형 : 트리 순회

6597번: 트리 복구

▸ 문제

창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다.

아래는 창영이가 만든 한 바이너리 트리이다.

                                               D
                                              / \
                                             /   \
                                            B     E
                                           / \     \
                                          /   \     \
                                         A     C     G
                                                    /
                                                   /
                                                  F

창영이는 후손들에게 물려주기 위해서, 만든 트리를 항상 종이에 적어놓는다. 이때, 트리를 프리오더 순회한 결과와 인오더로 순회한 결과를 적어 놓는다. 위의 트리를 프리오더로 순회하면 DBACEGF가 되고, 인오더로 순회하면 ABCDEFG가 된다. 창영이는 이 두 순서만 있으면, 트리를 만들 수 있다고 생각했기 때문에, 포스트오더로 순회한 결과는 적지 않았다.

몇 년이 지난 후, 종이를 보고 트리를 다시 만들려고 했다. 하지만 너무 귀찮은 나머지 프로그램을 작성하려고 한다. 트리를 프리오더와 인오더로 순회한 결과가 주어졌을 때, 포스트오더로 순회한 결과를 구하는 프로그램을 작성하시오.

▸ 입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있고, 프리오더로 순회한 결과와 인오더로 순회한 결과가 공백으로 구분되어져 있다. 두 문자열의 길이는 항상 같으며, 26자를 넘지 않는다.

▸ 출력

각 테스트 케이스에 대해서, 입력으로 주어진 트리를 포스트오더로 순회한 결과를 출력한다.

 

문제 풀이  

프리 오더, 인오더, 포스트오더 세 가지의 데이터 중 2가지만 있으면 쉽게 트리를 복구할 수 있다. 

• 전위순회(pre)는 Root → L  → R 이고,
• 중위순회(in)는 L → Root → R 이고,
• 후위순회(post)는 L → R → Root 이다.

첫 예제를 가지고 트리를 복구하면 다음과 같이 구할 수 있다. 전위순회 데이터로 루트 노드를 구하고 중위 순회에서 그 루트노드에 해당하는 구간을 찾아 Left와 Right로 구분해주면서 재귀를 돌려주면 된다.

 

트리 복구하기

 

설계

1. 전위 순회(pre), 중위 순회(in), 중위 순회 인덱스(inIdx)의 데이터를 입력받는다.
2. pre 데이터를 통해 루트 노드를 구하고 inIdx를 통해 in 데이터에 위치한 루트 노드의 인덱스를 구한다.
   1. int root = pre[idx];
   2. int rootIdx = inIdx[root];
3. 그렇게 구한 위치로 left, right 서브트리를 재귀로 나눈다.
   1. left 노드: recover(idx+1, left, rootIdx);
   2. right 노드: recover(idx+1+(rootIdx-left), rootIdx+1, right);
4. 후위 순회이므로 재귀가 반환되면서 나오는 root의 값들을 차례대로 저장한 다음 출력한다.

 

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static int[] pre, in, inIdx;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input;
		StringTokenizer st;
		try {
			while(true) {
				input = br.readLine();
				if(input.split(" ").length ==0) break;
				st = new StringTokenizer(input);
				String preOrder = st.nextToken();
				String inOrder = st.nextToken();
				
				int size = preOrder.length();
				pre = new int[size+1];
				in = new int[size];
                inIdx = new int[size];
				
				for(int i=0; i<size; i++) {
					pre[i] = preOrder.charAt(i)-'A';
					in[i] = inOrder.charAt(i)-'A';
					
				}
                for(int i=0; i<size; i++) {
					inIdx[in[i]] = i;
				}
				recover(0, 0, size);
				sb.append("\n");
			}
		} catch(Exception e) {
			
		}
		System.out.println(sb.toString());
	}
	
	static void recover(int idx, int left, int right) {
		if(left >= right) return;
		int root = pre[idx];
		int rootIdx = inIdx[root];
		
		recover(idx+1, left, rootIdx);
		recover(idx+1+(rootIdx-left), rootIdx+1, right);
		sb.append((char)(root+'A'));
	}
}