[백준 9934] 완전 이진 트리 (JAVA)

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

9934번: 완전 이진 트리

 

트리에 대해 복습하기 좋은 문제가 있어 가지고 왔다.

 

먼저 이진트리와 순회개념에 대해 숙지가 되어있지 않다면 하단의 링크를 참조하면 된다.

 

https://0bliviat3.tistory.com/32

[자료구조] 이진 트리와 순회의 구현(JAVA)

 

먼저 문제 분석을 하자면,

 

깊이가 k이고 2^k - 1의 노드를 갖는 완전이진트리를 중위순회한 입력이 주어지고

이 입력값으로 트리의 구조를 유추해

각 계층별로 왼쪽부터 오른쪽 순으로 출력해주면 되는 문제 이다.

 

우선 완전이진트리라고 나와있으나 깊이가 k이고 2^k - 1의 노드를 갖는 이란 조건으로

포화이진트리임을 알 수 있다.

그리고 중위 순회한 결과를 입력으로 주었으니 이 두가지 힌트를 가지고 문제를 해결하면 된다.

 

 

이 문제를 해결할때의 아이디어는 

중위순회한 포화이진트리의 결과가 나왔으니 역으로 다시 중위 순회하며

입력값을 순차적으로 다시 넣어주는 것이다. 이때 재귀호출로 깊이만 구분해준다면,

각 계층별 노드를 파악하여 트리구조를 유추해 낼 수 있다.

 

그럼 코드로 바로 풀이 해보도록 하겠다.

 

먼저 트리의 노드개수, 그리고 트리의 구조를 저장할 배열, 입력값을 순차적으로 넣어줄

StringTokenizer 객체를 선언해 주도록 하겠다.

 

	static int size;
	static ArrayList<String>[] tree;
	static StringTokenizer st;

 

이때 size는 입력받은 k값에 따라 2^k - 1 값을 갖고,

tree는 깊이 k를 길이로 갖는다. 루트노드는 이 배열의 0번 인덱스에 해당하는 값이 될 것이다.

 

그리고 중위 순회하며 입력받은 값을 순차적으로 넣어줄 메소드를 하나 선언해주도록 하겠다.

 

	static void inOrder(int node, int depth) {
		if(node > size) return;
		inOrder(node * 2,depth + 1);
		tree[depth].add(st.nextToken());
		inOrder(node * 2 + 1,depth + 1);
	}

 

재귀호출이 곧 깊이가 되므로 호출되는 만큼 더 하위 계층의 노드로 저장해주면 된다.

 

그리고 이제 출력형식에 맞춰 출력만 해주면 예제에 맞는 답을 내는것을 확인 할 수 있다.

 

 

아래는 코드의 전문이다.

 

package boj4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Boj9934 {
	
	static int size;
	static ArrayList<String>[] tree;
	static StringTokenizer st;
	
	static void inOrder(int node, int depth) {
		if(node > size) return;
		inOrder(node * 2,depth + 1);
		tree[depth].add(st.nextToken());
		inOrder(node * 2 + 1,depth + 1);
	}
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int k = Integer.parseInt(in.readLine());
		st = new StringTokenizer(in.readLine()," ");
		
		in.close();
		
		size = (int) Math.pow(2, k) - 1;
		
		tree = new ArrayList[k];

		for(int i = 0; i < k; i++) {
			tree[i] = new ArrayList<>();
		}
		
		inOrder(1,0);
		
		for(int i = 0; i < k; i++) {
			for(String node : tree[i]) {
				sb.append(node).append(' ');
			}
			sb.append('\n');
		}
		
		System.out.print(sb);
		
	}
	
	
}