[JAVA] 4256 - 트리 Preorder, Inorder, Postorder 순회

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

4256번: 트리

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class bj4256 {
    static int T;
    static int n;
    static int[] pre;
    static int[] in;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
 
        for(int t=0;t<T;t++) {
            n = Integer.parseInt(br.readLine());
 
 
            pre = new int[n];
            in = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                pre[i] = Integer.parseInt(st.nextToken()); //3 2 1 4
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                in[i] = Integer.parseInt(st.nextToken()); // 2 3 4 1
            }
 
            post(0, n, 0, sb);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    static void post(int start, int end, int cur, StringBuilder sb){
        for(int i=start;i<end;i++){
            if(pre[cur] ==in[i]){
                post(start, i, cur+1, sb); 
                post(i+1, end, cur+1+i-start, sb); 
                sb.append(pre[cur] + " ");
                System.out.println("start : " + start + ", i : " +  i + ", cur : " +  cur + " --> print : " +  pre[cur]);
            }
        }
    }
}
/*
* 먼저 생각할 것 : 전위 순회, 중위 순회, 후위 순회의 차이점. 몰까??
* 전위 순회는 root -> left child -> right child
* 중위 순회는 left child -> root -> right child
* 후위 순회는 left child -> right child -> root
*
* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
*
* 전위 순회에서 root를 찾을 수 있고, 중위 순회에서 left, right를 구별할 수 있다.
* 그 말인 즉슨, 중위 순회에서 찾은 left, right를 먼저 찾고
* 전위 순회에서 찾은 root를 돌려주면 후위 순회가 완성된다는 의미.
*
* */
 

해당 문제를 처음 봤을때는 , 코드가 아니라 손으로 풀었다. PostOrder이 아니라 pre, in만 보고 tree를 추측하는 알고리즘이다.

약간 부끄러우나 빨주노초파남보 순으로 읽으면 이해가 갈 것이다.

 

한마디로 전위 순회에서는 root를 찾고, 중위 순회에서는 root를 기준으로 left, right를 찾을 수 있다는 것이다.

 

[시도했으나 실패한 것]

python을 오래 쓰다보면 안좋은점이 너무 편리한 것에만 익숙해진다. 제공되는 메소드가 없이는 살지를 못한다.ㅎ

그래서 문자열을 합치는 부분이 너무 어려웠다. 이 부분을 충족시켜주는 StringBuilder라는 클래스 메소드를 사용하였다.

 

String 클래스는 문자열을 생성자로 해서 한번 새로운 인스턴스를 생성하면 문자열 값을 변경할 수 없다. 하지만 StringBuilder을 사용하면 문자열 값을 추가하거나 변경할 수 있다. JAVA는 싸피를 하면서 처음 써봤는데 이런게 있다니 ㅇ_ㅇ.. 했던게 너무 많다.

난 우물 안 개구리인듯..

아무튼 계속 하자면.. 먼저 StringTokenizer를 통해 공백으로 구분된 문자를 각각 Pre, in 리스트에 넣는다.

 

그다음 이 리스트의 원소들을 기반으로 후위순회를 진행한다.

후위순회는 아시다시피 left child-> right child-> root순으로 구분된다.

그말인 즉슨, 전위 순회의 root를 기반으로 중위 순회에서 left, right만 찾으면 해당 순서대로 다시 post를 돌리면 된다는 의미이다.

어렵지 않았다.

위에서 사용한 무지개 노트에서도 볼 수 있듯이 현재 내가 보고있는 root가 뭔지 계속 확인해주는 것도 필수이다.

 

1. Preorder과 Inorder을 비교하며 Root를 찾는다. 만약 같다면? cur이 바로 root였던 것이다.

2. Root, 즉 cur이면서 i 이다. 얘를 찾았으면, root의 left를 또 post를 돌려라. -->  post(start, i, cur+1, sb);

왜냐면?? 후위순회는 left->right->root니까.

3. root의 right도 따라서 post를 돌려주는 것이 인지상정이다.  post(i+1, end, cur+1+i-start, sb);

4. left->right->root라고 했으니 root를 post의 순서를 나타내는 문자열에 추가해준다.

이렇게 신나게 돌린 post가 끝났다면, 열심히 만들어진 문자열 sb를 출력하면 된다.