백준 1231. 중위 순회 :: 돼지개발자

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

"Complete Binary Tree를 배열로 구현하고 탐색"

이 문제는 Complete Binary (완전 이진트리라고함.. full , complete, perfect 등에 번역이 헷갈려 영어로 기억함.) 의 중위 순회를 구현하는 문제이다. 

Complete binary tree 는 배열로 구현가능하며, 배열 안에서 인덱스로 특정 노드의 부모, 자식 위치를 구할 수 있다.

아래와 같다.

노드 i의 부모 : (i-1) /2

노드 i의 왼쪽 자식 : (2*i) +1

노드 i의 오른쪽 자식 : (2*i) +2

참 쉽쥬?

그리고 중위 순회 (in-order) 의 경우 LDR 의 순서로 탐색한다, (왼쪽- 현재노드 - 오른쪽) 

따라서 구현도 쉽다. 현재 노드의 왼쪽 부터 쭉 타고 들어가고, 왼쪽이 없으면 현재 node를 출력하고, 다시 오른쪽으로 쭉~~~ 타고 들어간다.

static void inOrder(int node) {
    if((2*node) + 1 < n) inOrder((2*node) + 1);
    sb.append(map[node]);
    if((2*node) + 2 < n) inOrder((2*node) + 2);
}

그리고, Java 에서 다수의 문자를 출력할 때, StringBuilder 혹은 SgringBuffer 를 쓰는게 좋다.(PS의 경우 builder를 쓰는게 더 좋음, buffer는 동기화 처리가 되어 있어서 좀 느리다고함.) I/O 는 적게 일어나면 일어날수록 좋으므로....

System class의 함수들을 계속 호출하지말자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Solution {
    
    static int T = 10;
    static int n;
    static char[] map;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t =1;
        while(T-- > 0) {
            n = Integer.parseInt(br.readLine());
            map = new char[n];
            
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                st.nextToken();
                map[i] = st.nextToken().charAt(0);
                while(st.hasMoreTokens())
                    st.nextToken();
            }
            sb.append("#"+(t++)+" ");
            inOrder(0);
            System.out.println(sb.toString());
            sb.setLength(0);
        }
    }
    
    static void inOrder(int node) {
        if((2*node) + 1 < n) inOrder((2*node) + 1);
        sb.append(map[node]);
        if((2*node) + 2 < n) inOrder((2*node) + 2);
    }
}