BOJ(백준 온라인 저지) 2263번 with 자바[JAVA]

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

---

2024.06.02 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 #13 - Tree Traversal and Parsing

자료구조 및 알고리즘 #13 - Tree Traversal and Parsing

에 나온 Inorder 와 Postorder 를 통해 Preorder 를 추론하는 방법을 그대로 사용했다.

구현

Preorder 는 root 가 가장 먼저 나오는 방식의 순회이다.

Postorder 와 Inorder 를 통해 root 를 찾은 후 Preorder 에 넣어주면 된다.

 

예를 들어,

Inorder: 1 2 3 4 5 6 7

Postorder: 1 3 2 5 7 6 4

 

라면,

 

Postorder 를 통해 4가 최상위 root 임을 알 수 있고,

이를 Preorder 의 처음으로 넣어준다.

 

4가 root 임을 알았으니 Inorder 를 통해

4 앞에 있는 1,2,3 은 4의 왼쪽 서브트리,

4 뒤에 있는 5,6,7 은 4의 오른쪽 서브트리임을 알 수 있다.

 

위 과정을 한 단계라고 생각하면

이 단계를

Inorder: 1 2 3

Postorder: 1 3 2

와

Inorder: 5 6 7

Postorder: 5 7 6

에 대해 재귀적으로 호출함으로써 구현할 수 있다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N;
    public static int[] inorder;
    public static int[] postorder;
    public static ArrayList<Integer> preorder = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        inorder = new int[N];
        postorder = new int[N];

        // Inorder 초기화
        StringTokenizer stIn = new StringTokenizer(br.readLine());
        int index = 0;
        while(stIn.hasMoreTokens()){
            inorder[index++] = Integer.parseInt(stIn.nextToken());
        }

        // Postorder 초기화
        StringTokenizer stPost = new StringTokenizer(br.readLine());
        index = 0;
        while(stPost.hasMoreTokens()){
            postorder[index++] = Integer.parseInt(stPost.nextToken());
        }

        // Preorder 를 찾는 함수
        // 인자로 Inorder 와 Postorder 에서 사용할 부분수열의 시작과 끝 index를 받는다.
        find(0, inorder.length - 1, 0, postorder.length - 1);

        for(Integer i : preorder)
            System.out.print(i + " ");
    }

    private static void find(int inStartIdx, int inLastIdx, int posStartIdx, int posLastIdx) {
        // 시작 index 가 끝 index 보다 뒤 이면 그냥 종료한다.
        if(inStartIdx > inLastIdx || posStartIdx > posLastIdx)
            return;

        // Postorder 의 마지막 요소는 root 이므로, 바로 Preorder 에 넣어준다.
        int root = postorder[posLastIdx];
        preorder.add(root);

        // 왼쪽과 오른쪽 서브트리의 노드 개수를 파악하기 위해 root 의 index 를 구한다.
        int rootIdx = 0;
        for(Integer i : inorder){
            if(i == root)
                break;
            rootIdx++;
        }

        // root 의 index 를 통해 왼쪽과 오른쪽 서브트리의 노드 개수를 파악한다.
        int numOfLeft = rootIdx - inStartIdx;
        int numOfRight = inLastIdx - rootIdx;

        // 재귀 호출
        find(inStartIdx, inStartIdx + numOfLeft - 1, posStartIdx, posStartIdx + numOfLeft - 1);
        find(rootIdx + 1, rootIdx + numOfRight, posLastIdx - numOfRight, posLastIdx - 1);
    }
}

 

배움

 

재귀, 트리 순회