[swea] 7985. Rooted Binary Tree 재구성 D3 (자바)

7985. Rooted Binary Tree 재구성 D3

[문제]

성삼 회사에서 마지막 면접을 보게 된 당신에게 Rooted Binary Tree 재구성이라는 미션으로 주었다.

먼저 Rooted tree란 트리의 정점 중 하나가 root로 정해지고 간선의 양 끝점이 부모, 자식 관계를 맺게 만든 것이다.

Rooted binary tree는 그 중에서 이진 트리(binary tree)를 의미한다.

주어지는 정보는 tree를 중위 순회(inorder traversal)한 결과이다.

일반적으로 중위 순회(inorder traversal)를 통해 기존의 트리를 완벽히 복구하는 것이 불가능하다.

가능한 경우가 다양하기 때문이다.

따라서 성삼 회사에서는 tree가 항상 완전 이진 트리를 제공한다고 하였다.

높이가 K이며 정점의 개수가 2K-1인 tree를 의미한다.

중위 순회(inorder traversal)란 위와 같은 트리가 있을 때 L->T->R순으로 순회하는 것을 말한다.

따라서 위의 트리의 중위 순회(inorder traversal)한 결과는 3-2-7-5-6-1-4 이다.

당신은 면접에서 레벨 별로 정점 번호를 왼쪽부터 순서대로 대답해야 한다.

트리의 깊이와 중위 순회(inorder traversal) 결과를 줬을 때, 올바르게 대답하여서 면접에 합격하자.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 완전 이진 트리의 깊이 K(1 ≤ K ≤ 10) 이 주어진다.

두 번째 줄에는 [1,2K-1] 사이의 자연수들이 한 번씩 모두 나타난다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스마다 레벨 별로 왼쪽부터 정점 번호를 출력하라.
 

입력

2 3 3 2 7 5 6 1 4 2 2 1 3

// 테스트 케이스 개수 // 첫 번째 테스트 케이스, K = 3 // 두 번째 테스트 케이스, K = 2

 

출력

#1 5 2 1 3 7 6 4 #2 1 2 3

// 첫 번째 테스트 케이스 결과 // 두 번째 테스트 케이스 결과

 

[코드]

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


public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 1; i <= T; i++) {
        	int K = Integer.parseInt(br.readLine());
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	List<Integer> arr1=new ArrayList<>();
        	int size=(int)(Math.pow(2, K)-1);
        	for (int i2 = 0; i2 <size ; i2++) {
        		arr1.add(Integer.parseInt(st.nextToken()));        		
			}
        	
        	//int one=(int)(Math.floor(arr1.size()/2));
        	
        	List<Integer> arr2=new ArrayList<>();
        	boolean exit = false;
        	while (!exit) {
        		for (int i3 = 0; i3 < arr1.size(); ) {
        			arr2.add(arr1.get(i3));
        		    arr1.remove(arr1.get(i3));
        		    i3+=1;
        		    if(arr1.size()==0) {
        		    	exit=true;
        		    	break;        		    	
        		    }
        		}
        	}

    		System.out.println("#"+i+" "+arr2.get(arr2.size()-1));
    		arr2.remove(arr2.size()-1);
    		
    		int end=2;
        	for (int j1 = 0; j1 < K-1; j1++) {
        		List<Integer> arr3=new ArrayList<>();

        		for (int j2 = 0; j2 < end; j2++) {
        			arr3.add(arr2.get(arr2.size()-1));
        			arr2.remove(arr2.size()-1);		
				}
        		
    			end=end*2;
    			Collections.reverse(arr3);
    			

    			for (int j3 = 0; j3 < arr3.size(); j3++) {
    				System.out.print(arr3.get(j3)+" ");
				}
    			System.out.println();
        	}
        }
        br.close();
    }
}