[백준] Q2263 트리의 순회 JAVA

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

2263번: 트리의 순회

1. 문제의 유형 구분과 이해

Divide and Conquer >> Recursion (참조 : )

트리 자료구조의 이해 (참조 : )

 

트리 탐색 방법 중 Binary Tree에서 재귀를 활용하여 탐색하는 Preorder, Inorder, Postorder가 있다.

각각의 탐색 순서는 다음과 같다.

Preorder : Value - Left - Right

Inorder : Left - Value - Right

PostOrder : Left - Value - Right

 

문제에서 주어진 PostOrder와 Inorder를 통해 PreOrder를 구하는 문제이다.

 

2. 문제 접근 방법

주어진 Inorder와 PostOrder에 대해 먼저 큰 트리에 대해 생각해보자.

 

트리 형태

 

위와 같은 형태로 구분된다. 이 때 우리는 하나의 수 V를 특정할 수 있게 된다.

Preorder가 Value - Left - Right순서이기 때문에 우리는 하나의 트리 형태에서 'V'를 뽑아오고 
Left와 Right를 구분하여 다시 이 작업을 반복하면 되게 된다.

 

주의해야할 점이 하나 있는데, 이 부분에서 계속 헷갈려서 틀리게 작성했었다.

핵심은 Size

PostOrder에서는 값을 찾고, Inorder에서는 다시 Postorder에서의 구분을 지어주는 역할이라고 생각한다.

이후 각각 Inorder에 두개의 포인터를 Postorder에 두개의 포인터를 두어 구분하는데

Left쪽을 자꾸 생각하다 보니 pointer가 그대로 들어간다고 생각하는 오류를 범해서 시간이 많이 걸렸다.

PostOrder에서 알아낸 V값을 통해 Inorder에서 Left와 Right의 구분이 가능하고, 해당 사이즈 만큼

Postroder에서 주어진 범위 내에서 Left의 사이즈와 Right의 사이즈를 구분하여야한다.

 

트리 또한 재귀적으로 트리들이 모여 만들어져있는 형태이기 때문에 각각의 Left Tree와 Right Tree에 대해 같은 형태로 행해주면 된다.

 

/*
2022.01.07
문제번호 : Q2263_Review
이름 및 난이도 : 트리의 순회 Gold II
문제이해 
-----------------
1~n 인오더와 포스트 오더가 주어질 때 프리오더를 구하시오
preorder : VLR
inorder : LVR
postorder : LRV

Point는 트리의 사이즈에 따른다.
inorder의 쓰임은 사이즈를 계산하기 위한 두개의 포인터가 필요하고 (범위설정 영향)
postorder의 쓰임은 값을 V에서 뽑아내기 위해 필요하다.(값)
*/

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

public class Main {
    static int N;
    static int inorder[];
    static int postorder[];
    static StringBuilder sb;
    static int idx[];

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        inorder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        postorder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    public static void solve() {
        initData();
        findPreorder(0, N, 0, N);
        System.out.println(sb.toString());
    }

    public static void initData() {
        idx = new int[N + 1];
        for (int i = 0; i < N; i++) {
            idx[inorder[i]] = i;
        }
    }

    // 반개구간 [ ) >> size를 구하기 편리함 [a,b-1] == (a,b) size: b-a
    public static void findPreorder(int inStart, int inEnd, int postStart, int postEnd) {
        
        if (postEnd <= postStart )
            return;

        // find Value from postorder
        int V = postorder[postEnd - 1];
        sb.append(V).append(" ");
        int dividePoint = -1;

        // find divide Size from inorder >> 시간을 많이 잡아먹는다.
        // Algorithm Skill (미리 구해놓기)
        // for (int i = 0; i < N; i++) {
        // 	if (inorder[i] == V) {
        // 		dividePoint = i;
        // 		break;
        // 	  }
        // }
        dividePoint = idx[V];

        // inorder의 경우 dividePoint를 기준으로 나뉘게 된다.
        // postorder의 경우 inorder에서 구한 사이즈를 기준으로 나뉘게 된다.
        int size = dividePoint - inStart; // leftSize

        // LEFT
        findPreorder(inStart, dividePoint, postStart, postStart + size);
        // RIGHT
        findPreorder(dividePoint + 1, inEnd, postStart + size, postEnd - 1);
    }

}

 

3. 주의점

V를 구할 때 Inorder에서 어디있는지 찾기 위해 O(N) 선형적으로 탐색하게 되면, 

각각의 구분된 트리로 들어갈 때 마다 N만큼 돌게 되기 때문에 결국

O($N^2$/)만큼 돌게 된다. 이를 방지하기 위해 배열하나를 두고 미리 구해놓으면 빠르게 할 수 있다.

 

반복되는 연산을 최대한 피하기 위해 미리 저장해두는 괜찮은 방법이다.