Iyoungman Back-end Developer

BOJ 9934. 완전 이진 트리

2020-04-28
Algorithm
         

Problem

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


Think

  • 주어진 입력은 중위 순회를 의미한다.
  • 따라서 중위 순회를 알 때 -> 트리를 알아내는 문제이다.
  • 고민을 좀 하다가, 완전 이진 트리이므로 규칙성이 있을 것이라고 생각했다.
  • 성공은 했지만 보다 좋은 구현을 고민해봐야겠다.

  • 일부 참고한 문제.


Solved Code

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

/**
 * Created by iyoungman on 2020-04-28.
 */

public class Main {

    //정답을 담을 ArrayList
    private static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        init(k);//(1)

        int n = (int) Math.pow(2, k) - 1;
        int[] buildings = new int[n];

        String[] splits = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            buildings[i] = Integer.parseInt(splits[i]);
        }

        setBuildingNumsAtTree(n / 2, buildings, k, 1);//(2)

        print(k);//(7)
    }

    private static void init(int k) {
        for (int i = 0; i <= k; i++) {
            tree.add(new ArrayList<>());
        }
    }

    private static void setBuildingNumsAtTree(int index, int[] buildings, int k, int curLevel) {
        if (curLevel > k) {//(6)
            return;
        }

        //(3)
        ArrayList<Integer> numbersAtTheLevelOfTree = tree.get(curLevel);
        numbersAtTheLevelOfTree.add(buildings[index]);
        tree.set(curLevel, numbersAtTheLevelOfTree);

        //(4)
        int temp = (int) Math.pow(2, (k - curLevel - 1));
        int leftIndex = index - temp;
        int rightIndex = index + temp;

        //(5)
        if (leftIndex >= 0) {
            setBuildingNumsAtTree(leftIndex, buildings, k, curLevel + 1);
        }
        if (rightIndex < buildings.length) {
            setBuildingNumsAtTree(rightIndex, buildings, k, curLevel + 1);
        }
    }

    private static void print(int k) {
        for (int i = 1; i <= k; i++) {
            ArrayList<Integer> numbersAtTheLevelOfTree = tree.get(i);
            for (int building : numbersAtTheLevelOfTree) {
                System.out.print(building + " ");
            }
            System.out.println();
        }
    }

}


Solved Process

1) 정답을 담을 이중 ArrayList를 초기화한다.

2) 중위 순회이므로 (빌딩의 개수 N / 2)가 Root 노드이다.

3) 이중 ArrayList인 tree에서, 인자로 받은 curLevel을 이용하여 빌딩 번호를 저장할 ArrayList를 꺼낸다.

4) 중위 순회의 규칙성을 찾아, temp라는 변수를 만들었다.

현재 index에서 temp를 뺀 인덱스가 왼쪽 자식 노드 index

현재 index에서 temp를 더한 인덱스가 오른쪽 자식 노드 index

위와 같은 규칙성을 찾았다


5) 위에서 구한 leftIndex, rightIndex를 이용해 재귀적으로 함수를 호출한다. 이때 트리의 깊이(Level)을 +1 한다.

6) 주어진 트리의 깊이인 k보다 크면 재귀함수를 Return한다.

7) 정답을 출력한다.

Comments

Content