[BOJ] 9934번: 완전 이진 트리

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

9934번: 완전 이진 트리

 

문제

 

입력

첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.

둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다. 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2^k)에 포함된다.

 

출력

총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다. 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

 

난이도

실버 1

 

 

Sol

문제에서 주어진 트리는 가장 마지막 레벨을 제외한 모든 노드가 왼쪽 자식과 오른쪽 자식을 갖는 완전 이진 트리이고, 해당 방문 순서는 중위 순회이다. 주어진 방문 순서 input의 중앙이 루트 노드이고, 왼쪽과 오른쪽의 중앙이 그 다음 자식 노드임을 확인하고 분할 정복을 통해 풀었다. 범위의 중앙값을 찾아 트리에 넣고, 해당 범위의 왼쪽 범위와 오른쪽 범위에서 재귀함수를 다시 실행해나가면서 트리의 위에서 아래로 탐색해나갔다. 

public class B9934_완전이진트리 {
    static int K; // 완전 이진 트리의 깊이
    static int[] input;
    static List<ArrayList<Integer>> tree;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        K = Integer.parseInt(bf.readLine());
        StringTokenizer token = new StringTokenizer(bf.readLine());

        input = new int[(int)Math.pow(2, K) - 1];

        for(int i=0; i<input.length; i++){
            input[i] = Integer.parseInt(token.nextToken());
        }
        // input

        tree = new ArrayList<>();
        for(int i=0; i<K; i++){
            tree.add(new ArrayList<>());
        } // ArrayList를 담고 있는 ArrayList 생성

        search(0, input.length - 1, 0); // 루트 노드부터 한 노드씩 내려가면서 탐색
        // operation

        for(ArrayList<Integer> arr : tree){
            for(int i : arr){
                System.out.print(i + " ");
            }
            System.out.println();
        }
        // output
    }

    static void search(int start, int end, int depth){ // 시작 노드, 끝 노드, 깊이
        if(depth == K) return; // 탐색 종료

        int mid = (start + end) / 2;
        tree.get(depth).add(input[mid]);
        // 중앙값을 찾아 트리에 넣는다

        search(start, mid - 1, depth + 1); // 왼쪽 노드
        search(mid + 1, end, depth + 1); // 오른쪽 노드
    }
}

🙄

tree.get()...에서 IndexOutOfBoundException이 발생

-> ArrayList<Integer>를 담는 ArrayList를 만들어놓고 안에 ArrayList를 담아주지 않아 발생한 오류. 트리의 깊이 K만큼 tree.add(new ArrayList<>())를 실행해줌으로써 해결