[알고리즘 | 백준 ] 9934번 _ 완전 이진 트리

문제 출처

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

 

문제 요약

높이 K인 완전 이진 트리가 주어지고, 각 노드는 빌딩의 고유 번호가 붙어져 있다. 

상근이는 중위 순회 방식으로 각 빌딩을 순회하여 방문한 빌딩의 번호를 순차적으로 적었다. 

이를 바탕으로 각 레벨에 존재하는 빌딩의 번호를 출력하라. 

 

입력 예시 

2

2 1 3 

---------

3

1 6 4 3 5 2 7

 

우리는 입력 값만을 이용해 트리의 형태가 아래와 같음을 유추해야 한다. 

그렇다면 어떻게 유츄 할 수 있을까? 

 

 

입력 예시를 분석해 본 결과 나열된 노드에서 노드의 중앙값(start + end / mid에 위치한 노드)이 왼쪽 노드들과 오른쪽 노드들의 부모 노드임을 알 수 있었다. 

따라서 재귀적으로 mid값을 추출하면 각 레벨에 해당하는 부모 노드를 찾을 수 있다는 것이다. 

 

 

재귀적으로 이를 구현하면 아래와 같다. 

 

 

 

인덱스의 끝점, 시작점, 현재 레벨을 인자로 받는다. 

재귀적으로 인덱스 기준 mid값이 현재 level의 부모 노드임을 알 수 있다. 이를 각 level을 key값으로 갖는 hashmap에 추가하였다. 

재귀 종료 조건은 현재 레벨의 값이, 총 높이 height보다 큰 경우이다. 이때는 재귀조건을 종료한다. 

 

** 초반에 실수했던 부분

level을 1증가하여 넘겨주는 부분에 전위 연산자를 사용했었다. 전위 연산자, 후위 연산자는 level의 값 자체를 바꾸어 버리기 때문에 두번째 right subtree를 구하는 재귀문에서 level + 2 를 한 결과를 전달하게 되는 문제가 있다. 그리고 특히 후위 연산자의 경우 함수 매개변수로 현재 level을 전달하고 그 후에 함수가 종료된 후 level = level + 1을 하기 때문에 예상과 다른 문제가 발생할 수 있다. 이 또한 주의할 것!

 

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.KeyPair;
import java.util.*;
import java.util.stream.Collectors;

class Main {

    public static HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();

    public static void main(String[] args) throws IOException {

        ArrayList<Integer> arrayList = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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


        // Level에 따라 노드를 저장할 수 있도록 함.
        for(int i=0; i<height; i++){
            map.put(i,new ArrayList<Integer>());
        }

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

        int[] numbers = new int[st.countTokens()];
        for(int i=0; i<numbers.length; i++){
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0; int end = numbers.length-1;
        recursive(start,end,0,height-1,numbers);

        for (int i=0; i<height; i++){
            ArrayList<Integer> list = map.get(i);
            for(int num : list){
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }



    public static void recursive(int start, int end, int level, int height, int[] numbers) {

        if (level > height){
//            System.out.println("level : " + level + "height : "+ height);
            return;
        }

        int mid = (start + end) / 2   ;
        map.get(level).add(numbers[mid]);
//        System.out.println(level + ":" + numbers[mid]);

        recursive(start,mid-1,level+1,height,numbers);
        recursive(mid+1,end,level+1,height,numbers);
    }
}