TRAVERSAL 트리 순회 순서 변경 / ALGOSPOT

문제링크 : https://algospot.com/judge/problem/read/TRAVERSAL
제출링크 : https://algospot.com/judge/submission/detail/659612
자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/TRAVERSAL/src/Main.java

알고스팟의 TRAVERSAL 문제를 풀어보겠습니다. 이 문제는 바이너리트리를 사용하여 푸는 문제로, pre-order, in-order로 방문한 결과를 가지고, post-order로 방문한 결과를 출력하는 문제입니다.

1. 문제를 풀기전 떠올려야 할 내용이 바로, pre-order, in-order는 방문한 순서만 다르다는 점입니다. 따라서, pre-order로 방문한 리스트와 in-order로 방문한 리스트를, 집합으로 변환한다면, 2개의 집합은 같은 집합입니다.

이 문제는, pre-order의 특성과, in-order의 특성을 활용해서, 푸는 문제입니다. 먼저 pre-order의 특성에 대해 알아 보겠습니다.
pre-order로 순회한 값이 ArrayList의 alPre에 있다고 하면, alPre.get(0)은 root node의 값입니다. 이값은 in-order로 순회한, ArrayList인 alIn에 반드시 들어 있습니다. (앞의 #1 참고)

alPre.get(0)값은 root node의 값이기 때문에, root변수에 저장하구요, root가 alIn의 몇번째 순서에 들어 있는지 찾아서
즉, 아래와 같이 찾아서, root의 인덱스를 idxCenter 에 저장합니다.

int root = alPre.get(0);
int idxCenter = alIn.indexOf(root);

문제에서 주어진 첫번째 예제입력중에 in-order를 사용하면, idxCenter는 3이 되고, 그림으로 그려보면 아래와 같습니다.

27은 root node의 값이고, 위의 순서가 in-order 임으로, 위의 그림에서 왼쪽 subtree #1, 인덱스기준 02 구간과,
오른쪽 subtree #2 인덱스 기준 46 구간으로 나눌 수 있습니다. 아직은 #1과 #2를 어느 순서로 출력해야 올바른 post-order인지는 알 수 없지만, #1을 모두 출력한 뒤, #2를 모두 출력한 후, root node를 출력하면, 정답인 것은 알 수 있습니다.

다시 pre-order로 돌아와서, 제일 앞에 있는 것은 root 이고, 그 뒤에는 해당 트리의 왼쪽 subtree와, 오른쪽 subtree가 있지만,
pre-order만 가지고는, 2개의 subtree를 나눌 수가 없습니다. 여기서, 앞에서 in-order에서 찾은 #1과 #2가 2개의 트리를 나눠주는대 사용됩니다.

pre-order리스트는 제일앞에 root + 왼쪽 subtree + 오른쪽 subtree 형태의 리스트 입니다. 따라서, 왼쪽 subtree의 길이가 in-order에서 찾은 #1의 길이 이구요, 오른쪽 subtree의 길이가 #2의 길이 입니다.

정리하면, pre-order와 in-order는 아래와 같이 구성되어 있다는 것입니다.

• pre-order = root + left subtree + right subtree
• in-order = left subtree + root + right subtree

실제로 나눠보겠습니다.

첫번째 나누기
27 16 9 12 54 36 72
9 12 16 27 36 54 72

첫번째 나눈 왼쪽 subtree
16 9 12
9 12 16

첫번째 나눈 오른쪽 subtree
54 36 72
36 54 72

첫번째 subtree는 위와 같이 나누게 되구요, 실제로 끝까지 나누어 보면, 아래 그림과 같이 됩니다.

위와 같은 방법으로 pre-order, in-order 2개 리스트를 쪼개 나가다 보면, 언젠가는 subtree의 길이가 0이 되는 순간이 오고, 이것이 재귀호출되는 메서드 printPostOrder()의 stop condition이 됩니다. 따라서, printPostOrder() 메서드가 한번 호출 될 때 마다, 한개의 노드가 출력되어야할 순서를 알 수 있습니다.

time complexity를 계산해보면, printPostOrder()가 한번 호출 될 때 마다, 노드 한개의 위치를 알 수 있으니, O(N)이구요,
노드 한개의 위치를 찾기 위해서, idxCenter를 찾을 때 걸리는 시간, 이것이 또 O(N)입니다.
따라서, 아래 코드의 시간 복잡도는 O(N^2)이 되게 됩니다.

추가적으로, 아래 코드는 바이너리 트리를 만들어서, 각각 pre/in/post order로 출력하는 부분도 포함되어 있습니다. 공부하시는대 참고하시구요, 알고리즘 문제풀기 파이팅입니다 ~~!!

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * TRAVERSAL 트리 순회 순서 변경 / ALGOSPOT
 * 문제링크 : https://algospot.com/judge/problem/read/TRAVERSAL
 * 제출링크 : https://algospot.com/judge/submission/detail/659612 ← post order만 출력한 것
 * 제출링크 : https://algospot.com/judge/submission/detail/659648 ← binary tree를 만들어서, post order로 출력한 것
 */
public class Main {
    int N;
    ArrayList<Integer> alPre;  // pre-order
    ArrayList<Integer> alIn;  // in-order
    public enum LR {
        L, R
    }

    public void solve() throws IOException {
        int T = sc.nextInt();

        for(int t=0; t<T; ++t) {
            N = sc.nextInt();
            alPre = new ArrayList<Integer>();
            alIn = new ArrayList<Integer>();


            for(int i=0; i<N; ++i) {
                alPre.add(sc.nextInt());
            }
            for(int i=0; i<N; ++i) {
                alIn.add(sc.nextInt());
            }

//            printPostOrder(alPre, alIn);
//            printPostOrder(alPre.subList(1, idxCenter+1), alIn.subList(0, idxCenter));
//            printPostOrder(alPre.subList(idxCenter+1, n), alIn.subList(idxCenter+1, n));

            int root = alPre.get(0);
            int n = alPre.size();
            int idxCenter = alIn.indexOf(root);
            BNode<Integer> rootNode = new BNode(root);

            buildBinaryTree(alPre.subList(1, idxCenter+1), alIn.subList(0, idxCenter), rootNode, LR.L);
            buildBinaryTree(alPre.subList(idxCenter+1, n), alIn.subList(idxCenter+1, n), rootNode, LR.R);
//            println();
//            myPreOrder(rootNode);
//            println();
//            myInOrder(rootNode);
//            println();
            myPostOrder(rootNode);
            println();
        }
    }

    public void printPostOrder(List<Integer> alPre, List<Integer> alIn) throws IOException {
        if(alPre.size() == 0)
            return;

        int root = alPre.get(0);
        int n = alPre.size();

        int idxCenter = alIn.indexOf(root);
        printPostOrder(alPre.subList(1, idxCenter+1), alIn.subList(0, idxCenter));
        printPostOrder(alPre.subList(idxCenter+1, n), alIn.subList(idxCenter+1, n));

        print(root + " ");
    }

    public void buildBinaryTree(List<Integer> alPre, List<Integer> alIn, BNode<Integer> node, LR lr) {
        if(alPre.size() == 0)
            return;

        int center = alPre.get(0);
        int n = alPre.size();
        BNode<Integer> childNode = new BNode(center);
        if(LR.L == lr) {
            node.mL = childNode;
        }
        else {
            node.mR = childNode;
        }

        int idxCenter = alIn.indexOf(center);
        buildBinaryTree(alPre.subList(1, idxCenter+1), alIn.subList(0, idxCenter), childNode, LR.L);
        buildBinaryTree(alPre.subList(idxCenter+1, n), alIn.subList(idxCenter+1, n), childNode, LR.R);
    }

    public void myPreOrder(BNode<Integer> node) throws IOException {
        if(null == node)
            return;

        int v = (int)node.mV;
        print(v + " ");

        myPreOrder(node.mL);
        myPreOrder(node.mR);
    }

    public void myInOrder(BNode node) throws IOException {
        if(null == node)
            return;

        myInOrder(node.mL);

        int v = (int)node.mV;
        print(v + " ");

        myInOrder(node.mR);
    }

    public void myPostOrder(BNode node) throws IOException {
        if(null == node)
            return;

        myPostOrder(node.mL);
        myPostOrder(node.mR);

        int v = (int)node.mV;
        print(v + " ");
    }
//        int n = ;
//        for(int i=0; i<n; ++i) {
//
//        }

//        int n = ;
//        for(int j=0; j<n; ++j) {
//
//        }

//        int n = ;
//        for(int i=0; i<n; ++i) {
//            for(int j=0; j<n; ++j) {
//
//            }
//        }

//        int N = ;
//        for(int i=0; i<n; ++i) {
//            for(int j=0; j<n; ++j) {
//                for(int k=0; k<n; ++k) {
//
//                }
//            }
//        }

    public void _solve() throws IOException {
        solve();
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main._solve();
    }

    public class BNode<TV> extends Node {
        BNode<TV> mL;
        BNode<TV> mR;

        BNode(TV v) {
            super(v);
        }
    }

    public class Node<TV> {
        public TV mV;

        Node(TV v) {
            set(v);
        }

        public void set(TV v) {
            mV = v;
        }
    }

    public int[][] pSum2D(int[][] dt) {
        int[][] pSum2D = new int[dt.length][dt[0].length];
        return _prefixSum2D(dt, pSum2D, dt.length, dt[0].length);
    }

    public int[][] pSum2D(int[][] dt, int[][] pSum2D) {
        return _prefixSum2D(dt, pSum2D, dt.length, dt[0].length);
    }

    public int[][] _prefixSum2D(int[][] dt, int[][] pSum2D, int I, int J) {
        pSum2D[0][0] = dt[0][0];
        for(int j=1; j<J; ++j) {
            pSum2D[0][j] = dt[0][j] + pSum2D[0][j-1];
        }

        for(int i=1; i<I; ++i) {
            pSum2D[i][0] = dt[i][0] + pSum2D[i-1][0];
        }

        for(int i=1; i<I; ++i) {
            for(int j=1; j<J; ++j) {
                pSum2D[i][j] = dt[i][j] + pSum2D[i-1][j] + pSum2D[i][j-1] - pSum2D[i-1][j-1];
            }
        }

        return pSum2D;
    }

    public int area2DbyCnt(int[][] pSum2D, int i1, int j1, int i2, int j2) {
        return area2DbyIdx(pSum2D, i1-1, j1-1, i2-1, j2-1);
    }

    public int area2DbyIdx(int[][] pSum2D, int i1, int j1, int i2, int j2) {
        int r = pSum2D[i2][j2];

        if(i1>0)
            r -= pSum2D[i1-1][j2];
        if(j1>0)
            r -= pSum2D[i2][j1-1];

        if((i1>0) && (j1>0))
            r += pSum2D[i1-1][j1-1];

        return r;
    }

    public int[][] rotate90(int[][] a, int N) {
        int[][] tp = new int[N][N];

        for(int i=0; i<N; ++i) {
            for(int j=0; j<N; ++j) {
                tp[i][j] = a[N-1-j][i];
            }
        }

        return tp;
    }

    public int[][] rotate180(int[][] a, int N) {
        int[][] tp = new int[N][N];

        for(int i=0; i<N; ++i) {
            for(int j=0; j<N; ++j) {
                tp[N-i-1][N-j-1] = a[i][j];
            }
        }

        return tp;
    }

    public int[][] rotate270(int[][] a, int N) {
        int[][] tp = new int[N][N];

        for(int i=0; i<N; ++i) {
            for(int j=0; j<N; ++j) {
                tp[N-1-j][i] = a[i][j];
            }
        }

        return tp;
    }

    public void flip_h(int[][] a, int N) {
        for(int i=0; i<N; ++i) {
            for(int j=0; j<N/2; ++j) {
                int tp = a[i][N-j-1];
                a[i][N-j-1] = a[i][j];
                a[i][j] = tp;
            }
        }
    }

    public void flip_v(int[][] a, int N) {
        for(int i=0; i<N/2; ++i) {
            for(int j=0; j<N; ++j) {
                int tp = a[N-i-1][j];
                a[N-i-1][j] = a[i][j];
                a[i][j] = tp;
            }
        }
    }

    public int[][] clone2D(int[][] src) {
        int N = src.length;
        int[][] dst = new int[N][N];

        for (int i=0; i<N; i++) {
            System.arraycopy(src[i],0, dst[i],0, N);
        }

        return dst;
    }

    public class Pair<K, V> extends _Pair implements Comparable {
        public Pair(K key, V value) {
            super(key, value);
        }

        @Override
        public int compareTo(Object o) {
            Pair other = (Pair)o;
            int k1 = Integer.parseInt(this.getKey().toString());
            int k2 = Integer.parseInt(other.getKey().toString());

            if((k1 - k2) == 0) {
                int v1 = Integer.parseInt(this.getValue().toString());
                int v2 = Integer.parseInt(other.getValue().toString());
                return v1 - v2;
            }

            return k1 - k2;
        }
    }

    // http://cr.openjdk.java.net/~vadim/8140503/webrev.01/modules/base/src/main/java/javafx/util/Pair.java.html
    public class _Pair<K,V> {
        private K key;
        public K getKey() { return key; }
        private V value;
        public V getValue() { return value; }
        public _Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o instanceof _Pair) {
                _Pair pair = (_Pair) o;
                if (key != null ? !key.equals(pair.key) : pair.key != null) return false;
                if (value != null ? !value.equals(pair.value) : pair.value != null) return false;
                return true;
            }
            return false;
        }
    }

    // Normally used MIN/MAX number
    public final int _1087654321 = 1087654321;
    public final int __1087654321 = -1087654321;
    public final int _987654321 = 987654321;
    public final int __987654321 = -987654321;

    // Commonly used numbers as a divider of mod operation to prevent overflow
    public final int _10_007 = 10007;
    public final int _1_000_000_007 = 1000000007;
    final int MOD = _1_000_000_007;

    public void print(int v) throws IOException {
        print(v+"");
    }

    public void print(String s) throws IOException {
        bw.write(s);
    }

    public void println() throws IOException {
        print("\n");
    }

    public void println(int a) throws IOException {
        print(a+"\n");
    }

    public void println(long a) throws IOException {
        print(a+"\n");
    }

    public void println(double a) throws IOException {
        print(a+"\n");
    }

    public void println(String s) throws IOException {
        bw.write(s+"\n");
    }

    // -1
    public final int MINUS_1 = -1;

    // 4 ways
    public int[] d4i = new int[]{-1, 1, 0, 0};
    public int[] d4j = new int[]{0, 0, -1, 1};

    // 8 ways
    public int[] d8i = new int[]{-1, 1, 0, 0,  -1, -1, 1, 1};
    public int[] d8j = new int[]{0, 0, -1, 1,  -1, 1, 1, -1};

    // Initialize 2D arrays with value v
    public void fill2D(int[][] _2D, int v) {
        for(int[] _1D: _2D) {
            Arrays.fill(_1D, v);
        }
    }

    public void fill2D(long[][] _2D, long v) {
        for(long[] _1D: _2D) {
            Arrays.fill(_1D, v);
        }
    }

    public void fill2D(double[][] _2D, double v) {
        for(double[] _1D: _2D) {
            Arrays.fill(_1D, v);
        }
    }

    public void print2D(int[][] dp) throws IOException {
        print("    ");

        for(int j=0; j<dp[0].length; ++j){
            print(SS(j)+j + " ");
        }
        println();

        for(int i=0; i<dp.length; ++i){
            print(SS(i)+i+"|");
            for(int j=0; j<dp[0].length; ++j){
                print(SS(dp[i][j])+dp[i][j] + " ");
            }
            println();
        }
    }

    public void print2D(long[][] dp) throws IOException {
        print("    ");

        for(int j=0; j<dp[0].length; ++j){
            print(SS(j)+j + " ");
        }
        println();

        for(int i=0; i<dp.length; ++i){
            print(SS(i)+i+"|");
            for(int j=0; j<dp[0].length; ++j){
                print(SS(dp[i][j])+dp[i][j] + " ");
            }
            println();
        }
    }

    public final int LENGHT_OF_NUMBER = 3;
    /**
     * Generate space string for alignment when we print 2D arrays.
     * its length is LENGHT_OF_NUMBER - the length of number
     * Basically, we assume that number a is less than 1000.
     * So, LENGHT_OF_NUMBER is 3 by default.
     * @param a
     * @return
     */
    public String SS(int a) {
        String s = a+"";
        int l = LENGHT_OF_NUMBER - s.length();
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<l; ++i) {
            sb.append(" ");
        }

        return sb.toString();
    }

    public String SS(long a) {
        String s = a+"";
        int l = LENGHT_OF_NUMBER - s.length();
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<l; ++i) {
            sb.append(" ");
        }

        return sb.toString();
    }

    // Initialize 3D arrays with value v
    public void fill3D(int[][][] _3D, int v) {
        for(int[][] _2D: _3D) {
            for(int[] _1D: _2D) {
                Arrays.fill(_1D, v);
            }
        }
    }

    // GCD
    int GCD(int a, int b) {
        if(0 == b) {
            return a;
        }

        return GCD(b, a%b);
    }

    long GCD(long a, long b) {
        if(0 == b) {
            return a;
        }

        return GCD(b, a%b);
    }

    boolean IsEven(int a) {
        return (a>>1) == ((a>>1)<<1);
    }

    boolean IsOdd(int a) {
        return (a>>1) != ((a>>1)<<1);
    }

    boolean IsEven(long a) {
        return (a>>1) == ((a>>1)<<1);
    }

    boolean IsOdd(long a) {
        return (a>>1) != ((a>>1)<<1);
    }

    public Reader sc = new Reader();
//    Sometimes, Reader class cause unknown problem, when I submit my java code to judge server.
//    For more detail, please see https://algospot.com/forum/read/4731/
//    public Scanner sc = new Scanner(System.in);

    public BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    public class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String nextLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }

//    public void test_matrix_methods() throws IOException {
//        // Test Case 1
//        int m1[][] = { {1, 2, 3, 4},
//                {5, 6, 7, 8},
//                {9, 10, 11, 12},
//                {13, 14, 15, 16} };
//
//        // Tese Case 2
//        int m2[][] = { {1, 2, 3},
//                {4, 5, 6},
//                {7, 8, 9} };
//
//        println("Matrix Original");
//        print2D(m1);
//
//        println("Matrix Rotate 90");
//        print2D(rotate90(m1, m1.length));
//
//        println("Matrix Rotate 180");
//        print2D(rotate180(m1, m1.length));
//
//        println("Matrix Rotate 270");
//        print2D(rotate270(m1, m1.length));
//
//        println("Matrix Flip Horizontal");
//        int[][] m1h = clone2D(m1);
//        flip_h(m1h, m1h.length);
//        print2D(m1h);
//
//        println("Matrix Flip Vertical");
//        int[][] m1v = clone2D(m1);
//        flip_v(m1v, m1v.length);
//        print2D(m1v);
//
//        println();
//
//        println("Matrix Original");
//        print2D(m2);
//
//        println("Matrix Rotate 90");
//        print2D(rotate90(m2, m2.length));
//
//        println("Matrix Rotate 180");
//        print2D(rotate180(m2, m2.length));
//
//        println("Matrix Rotate 270");
//        print2D(rotate270(m2, m2.length));
//
//        println("Matrix Flip Horizontal");
//        int[][] m2h = clone2D(m2);
//        flip_h(m2h, m2h.length);
//        print2D(m2h);
//
//        println("Matrix Flip Vertical");
//        int[][] m2v = clone2D(m2);
//        flip_v(m2v, m2v.length);
//        print2D(m2v);
//    }
//
//    public void test_pSum2D_methods() throws IOException {
//        // Test Case 1
//        int m1[][] = { {1, 1, 1, 1},
//                {1, 1, 1, 1},
//                {1, 1, 1, 1},
//                {1, 1, 1, 1} };
//
//        println("Matrix Original");
//        print2D(m1);
//
//        int[][] m1pSum2D = new int[m1.length][m1[0].length];
//        println("pSum2D");
//        pSum2D(m1, m1pSum2D);
//        print2D(m1pSum2D);
//
//        println(area2DbyIdx(m1pSum2D, 1, 1, 3, 3));
//        println(area2DbyIdx(m1pSum2D, 0, 0, 3, 3));
//        println(area2DbyIdx(m1pSum2D, 0, 1, 3, 3));
//        println(area2DbyIdx(m1pSum2D, 1, 0, 3, 3));
//    }
}