문제 4256번 (실패)

소스코드 (구글링을 통해 풀었습니다)

import java.io.*;
import java.util.StringTokenizer;
public class boj4256 {
    static int[] pre, in;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            pre = new int[n+1];  in = new int[n+1];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                pre[j] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                in[j] = Integer.parseInt(st.nextToken());
            }
            traversal(0,0,n);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    static void traversal(int root, int s, int e){
        int rootIdx = pre[root];
        for (int i = s; i < e; i++) {
            if(in[i] == rootIdx){
                traversal(root+1, s,i);
                traversal(root+1+i-s, i+1, e);
                sb.append(rootIdx + " ");
            }
        }
    }
}

풀이 접근

• 입력 예시의 2번째 예시를 가지고 설명할 것이다.

1. preorder와 inorder 방식이 주어질 때 postorder를 구하는 문제이다.
2. preorder의 첫 숫자는 트리의 root 값이다.
3. root 값을 inorder에서 찾아보면 4번 idx에 있는 것을 볼 수 있고, root 값을 기준으로 왼쪽은 왼쪽노드, 오른쪽은 오른쪽 노드의 개수이다.
4. 그렇다면 inorder에서 root 인덱스에1을 더한 값으로 preorder에서 root의 왼쪽 자식노드의 idx이고, inorder에서root인덱스에 1을 더한 값에 탐색 시작지점인 s라는 변수를 빼면, preorder의 오른쪽 자식노드의idx가 나올 것이다.
5. 이런 방식을 제귀적으로 호출하여 postorder방식을 출력할 수 있다.

문제 핵심

• 제귀함수
• 분할정복
• 트리에 대한 이해