[SWEA] 1231 - 중위순회 (Java)

Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD

" 트리는 완전 이진 트리 형식으로 주어짐 & Inorder 형식으로 읽기 "

---

Logic

이진트리(Binary Tree) : 각 노드가 최대 두개의 자식 노드를 갖는 트리이다. 즉, 각 노드는 자식이 없거나 1개이거나 2개이다.
완전 이진트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 꽉 차 있는 상태인 트리이다. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽부터 오른쪽으로 채워져야 한다.
포화 이진트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

• Preorder(전위순회): 루트 방문 -> 왼쪽 자식 방문 -> 오른쪽 자식 방문
• Inorder(중위순회): 왼쪽 자식 방문 -> 루트 방문 -> 오른쪽 자식 방문
• Postorder(후위순회): 왼쪽 자식 방문 -> 오른쪽 자식 방문 -> 루트 방문

Approach

자바에서 트리를 구성할때 1차원 배열, 2차원 배열, 클래스 같은 방법으로 구현할 수 있다.
근데 이 문제는 '완전 이진 트리 형식'으로 주어지기 때문에 1차원 배열으로도 구현할 수 있다.

입력 순서대로 1차원 배열에 알파벳을 넣고 Inorder 순서대로 찾아서 StringBuffer에 넣어서 한꺼번에 읽어주면 된다! (입력받는게 더 어려운거 같기도ㅋㅎ)

static void inOrder(int idx) {
        if(idx>num)
            return;
        inOrder(2*idx); //루트 부르기
        sb.append(arr[idx]); //현재 알파벳 저장하기
        inOrder(2*idx+1); //오른쪽 자식 부르기
}

---

Code

package SWEA;

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

public class swea_1231 {
    static int num;
    static char[] arr;
    static int answer;
    static StringBuffer sb;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        

        for(int i=1; i<=10; i++) {
            num = Integer.parseInt(br.readLine());
            arr = new char[num+1];
            sb = new StringBuffer();

            //입력값 받기
            for(int j=1; j<=num; j++) {
                StringTokenizer str = new StringTokenizer(br.readLine());
                str.nextToken();
                arr[j] = str.nextToken().charAt(0);
                
            }
            
            inOrder(1);

            System.out.println("#"+i+" "+sb.toString());
        }
    }
    static void inOrder(int idx) {
        if(idx>num)
            return;
        inOrder(2*idx);
        sb.append(arr[idx]);
        inOrder(2*idx+1);
    }
}