[Java] 백준 2263번 트리의 순회 - 분할정복법

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

2263번: 트리의 순회

 

Inorder, Postorder를 보고 Preorder의 순서를 예상해 출력하는 문제다.

Postorder의 마지막에 root가 들어온다는 점을 이용해

Inorder에서 루트의 위치를 찾아 그를 중심으로

두 개의 트리로 분할해서 분할정복하는 문제였다.

 

package class4;

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

public class g2_2263{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static int[] in, post;
    static int n;

    static int[] inIndex;
    public static void main(String[] args){
        n = fs.nextInt();
        in = new int[n];
        post = new int[n];
        inIndex = new int[n+1];

        for (int i=0;i<n;i++){
            in[i] = fs.nextInt();
            inIndex[in[i]] = i;
        }
        for (int i=0;i<n;i++){
            post[i] = fs.nextInt();
        }

        solve(0, n-1, 0, n-1);

        pw.close();
    }

    static void solve(int inStart, int inEnd, int postStart, int postEnd){
        if (inStart > inEnd || postStart > postEnd){
            return;
        }

        int root = post[postEnd];
        int ptr = inIndex[root];
        pw.printf("%d ", root);

        int size = ptr - inStart - 1;
        solve(inStart, ptr - 1, postStart, postStart + size);
        solve(ptr + 1, inEnd, postStart + size + 1, postEnd - 1);
    }

//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}