[JAVA]백준 9934번: 완전 이진 트리

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

9934번: 완전 이진 트리

1. 문제 설명

 

문제

• 깊이가 K인 완전 이진트리가 주어진다.
• 상근이가 어떤 순서로 도시를 방문했는지 순서가 주어졌을 때, 각 레벨에 맞는 빌딩의 번호를 구하는 문제

조건

• 1 <=K <=10

 

2. 풀이

 

중위 순회를 통해 빌딩의 레벨을 구할 수 있다.

 

완전 이진트리이기 때문에 왼쪽을 left, 오른쪽을 right라 했을 때 부모는 left+right/2 인덱스이다.

 

이를 이용해서, 부모를 먼저 탐색하고 그 후 왼쪽 자식, 오른쪽 자식을 탐색해나가면 된다.

 

레벨 순서대로 출력을 해야 했기에 큐를 사용해서 구현했다.

 

*로직

1. 0, 2^K-2부터 탐색을 시작한다.

2. 부모를 탐색하고 왼쪽 자식, 오른쪽 자식 순서대로 큐에 삽입한다.

3. 현재 레벨이 끝나면 개행한다.

 

3. 코드

// JAVA 11 , 메모리 : 14364KB, 시간 : 132ms

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Queue<Point> queue = new LinkedList<>();
        int qSize, mid;
        Point now;

        int K = Integer.parseInt(br.readLine());

        int num = (int) Math.pow(2, K) - 1;

        int[] list = new int[num];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int x = 0; x < num; x++) {
            list[x] = Integer.parseInt(st.nextToken());
        }

        queue.add(new Point(0, num - 1));

        while (!queue.isEmpty()) {

            qSize = queue.size();

            for (int x = 0; x < qSize; x++) {

                now = queue.poll();

                // 부모
                mid = (now.left + now.right) / 2;

                sb.append(list[mid]).append(" ");

                if (now.left != now.right) {
                    // 왼쪽 자식
                    queue.add(new Point(now.left, mid - 1));
                    // 오른쪽 자식
                    queue.add(new Point(mid + 1, now.right));
                }


            }

            sb.append("\n");
        }

        System.out.print(sb);

    }

    public static class Point{
        int left, right;

        Point(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }




}