[백준] 9934 완전 이진트리: Java - S1

9934번: 완전 이진 트리

 

1. 알고리즘

완전 이진 트리

 

2. 해결책
중위 순회의 중심이 루트인 것을 이용

 

3. 접근한 방법

해야될 일 : 중심 순회 결과로 트리 구성하라
중위 순위 결과를 가지고 알아낼 수 있는것이 뭐지?

1. DFS 탐색과 결과가 같다. 하지만 루트는 어떻게 알아내고, 트리관계는 어떻게 알아내지? -> 불가능
2. 인덱스를 이용할까. 이 문제는 완전 이진 트리. 자식 노드는 부모 인덱스 i의 2_i, 2_i+1이다.
   1. 부모 인덱스는 어떻게 구하지? 이 문제는 루트나 정해진 순서가 없는데?알아낸 것 : 현재 리스트의 정 가운데가 루트이다.
   2. 우선 전체 인덱스에서 나누기 2 해봐서 루트가 나오는지 알아낸다. 나온다!

 

4. 해결법

재귀함수로 리스트를 쪼개가며, 각 레벨의 요소를 알아낸다. 쪼갤 때는 삽입한 요소는 제외한다.

 public static void solution(int depth, int start, int end){

        int n = (int) Math.floor((double) (start+end)/2);
        // 현재 레벨에 요소 삽입
        ans[depth].add(nums.get(n));

        if(end - start ==0){
            return;
        }
        solution(depth+1, start, n-1);
        solution(depth+1, n+1, end);
    }

 

 

 

5. 전체 코드

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

public class Main {

    public static int K;
    public static ArrayList<Integer> nums;
    public static ArrayList<Integer> [] ans;
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        K = Integer.parseInt(br.readLine());
        nums = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 노드 정보 입력 받기 (중위 순회 결과)
        while(st.hasMoreElements()){
            nums.add(Integer.parseInt(st.nextToken()));
        }
        ans = new ArrayList[K];
        for(int i=0; i<ans.length; i++){
            ans[i] = new ArrayList<>();
        }

        solution(0, 0, nums.size()-1);

        for(ArrayList<Integer> line : ans){
            for(int num : line){
                bw.write(num +" ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();

    }

    public static void solution(int depth, int start, int end){

        int n = (int) Math.floor((double) (start+end)/2);
        // 현재 레벨에 요소 삽입
        ans[depth].add(nums.get(n));

        if(end - start ==0){
            return;
        }
        solution(depth+1, start, n-1);
        solution(depth+1, n+1, end);
    }

}