[JAVA] SWEA D3 / 7985. Rooted Binary Tree 재구성

 

코드

Map의 Key에 depth를 저장하고, value에는 출력할 값을 List로 저장하였습니다.

1 : 5

2 : 2, 1

3 : 3, 7, 6, 4

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

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 t = 1; t <= T; t++) {
            int n = Integer.parseInt(br.readLine());

            String[] inputs = br.readLine().split(" ");
            int[] arr = new int[inputs.length];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = Integer.parseInt(inputs[i]);
            }

            Map<Integer, List<Integer>> map = new HashMap<>();
            bfs(arr, 0, arr.length - 1, map, 1);

            System.out.print("#" + t + " ");
            for (int i = 1; i < map.size(); i++) {
                List<Integer> values = map.get(i);
                for (int j = 0; j < values.size(); j++) {
                    System.out.print(values.get(j) + " ");
                }
                System.out.println();
            }
        }
    }

    static void bfs(int[] arr, int s, int e, Map<Integer, List<Integer>> map, int cnt) {
        int mid = (s + e) / 2;

        map.putIfAbsent(cnt, new ArrayList<>());
        map.get(cnt).add(arr[mid]);

        if (s >= e) {
            return;
        }

        bfs(arr, s, mid, map, cnt + 1);
        bfs(arr, mid + 1, e, map, cnt + 1);
    }
}