Java 백준 9934 완전 이진 트리

백준 링크

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

9934번: 완전 이진 트리

 

---

문제

입력

출력

입출력 예시

---

제출한 코드

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;

	static int n;
	static int[] data;
	static List<Integer>[] layer;

	public static void main(String[] args) throws Exception {
		init();
		run();
	}

	private static void init() throws Exception {
		n = Integer.parseInt(br.readLine());
        // 각 level마다 노드를 저장할 List
		layer = new List[n + 1];
		for (int i = 1; i <= n; i++) {
			layer[i] = new ArrayList<Integer>();
		}
        
		data = new int[(int) Math.pow(2, n) - 1];
		int dataLen = (int) Math.pow(2, n) - 1;

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < dataLen; i++) {
			data[i] = Integer.parseInt(st.nextToken());
		}
	}

	private static void run() {
    	// 로직 시작
		recur(0, (int) Math.pow(2, n) - 1, 1);
        // 정답 출력
		for(int i = 1; i <= n ; i++) {
			for(int output : layer[i]) {
				System.out.print(output + " ");
			}
            System.out.println();
		}
	}

	private static void recur(int start, int end, int depth) {
    	// 주어진 Level까지 진행
		if (depth > n) {
			return;
		}
        
        // 추가할 데이터
		int now = (end + start) / 2;
        // 해당 level에 추가
		layer[depth].add(data[now]);
        
        // 좌 우 퍼트리기
		recur(start, now - 1, depth + 1);
		recur(now + 1, end, depth + 1);
	}
}

 

1. 완전이진트리가 무엇인지 다시 한번 확인한다.

2. 완전 이진트리는 2^n-1개 만큼 노드를 가지고 있고 좌우가 균형을 이루고 있는 모양이다.

3. 전체 범위에서 중앙에 위치하는 값이 해당 level에 속한 값이다.

4. 병합 정렬과 비슷한 방식으로 전체 데이터를 재귀를 이용해 타고 들어가면서 해당 level의 값을 찾아준다.