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

- 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

// - 중위 순회 문제 
public class Main {
    static int K; // 트리 깊이 // 2
    static int size; // 트리 노드 수 
    static int[] num; // 초기 중위 순회 결과 저장
    static ArrayList<Integer>[] tree; // 각 레벨별로 노드를 저장할 리스트

    public static void main(String[] args) throws IOException{
        // 입력값 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 결과값 출력 
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        

        K = Integer.parseInt(br.readLine()); // 2

        StringTokenizer st = new StringTokenizer(br.readLine()); // 2 1 3

        // 1. 트리 총 노드수 계산
        // 깊이가 K인 완전 이진 트리는 총 2^K - 1개의 노드로 이루어짐
        // k = 2 , 2^2 - 1 = 3개
        size = (int) (Math.pow(2, K) - 1); // 3 

        // num 초기화 // 2 1 3 들어가야함 
        num = new int[size + 1];

        // 3. 레벨별로 노드를 저장할 리스트 초기화
        // 트리의 레벨은 1부터 K까지 존재하므로, 0번째 인덱스를 사용하지 않고, 
        // 1번째 인덱스부터 K번째 인덱스까지 사용하기 위해 배열의 크기를 K + 1로 설정
        tree = new ArrayList[K + 1]; // 레벨 1, 레벨 2 ..
        for(int i = 0; i <= K; i++) {
            tree[i] = new ArrayList<>();
        }

        // 2. 중위 순회 결과 저장 [2 , 1, 3]
        int index = 1;
        while(st.hasMoreTokens()){
            num[index++] = Integer.parseInt(st.nextToken());
        }


        // 4. 중위 순회 결과를 이용해 트리 구성 및 각 레벨에 노드 추가
        search(1,1, size);

        // 각 레벨에 있는 빌딩 정보 bw에 저장
        for(int i = 1; i <= K; i++) {
            for(int j = 0; j < tree[i].size(); j++) {
                bw.write(tree[i].get(j) + " ");
            }
            bw.newLine();
        }

        // 결과 출력
        bw.flush();

        bw.close();
        br.close();
    }

    // 중위 순회 특성을 이용하여 트리를 구성하고 각 레벨에 맞는 빌딩 값들을 저장
    private static void search(int depth, int start, int end) {
        int mid = (start + end) / 2; // 현재 서브트리의 루트 노드 위치(중간 지점)
        tree[depth].add(num[mid]); // 현재 레벨에 루트 노드 추가 

        // 단말 노드(자식이 없는 노드)일 때 재귀 종료
        if(depth == K) return;

        // 왼쪽 서브트리 구성
        search(depth + 1, start, mid - 1);

        // 오른쪽 서브트리 구성
        search(depth + 1, mid + 1, end);
    }
  
}

 

---

- 코드 설명

 

 

[ 문제 해결 순서 ]

1. 입력받기
2. 트리의 총 노드 수 계산
3. 중위 순회 결과 저장
4. 레벨별로 노드를 저장할 리스트 초기화
5. 중위 순회 결과를 이용해 트리 구성 및 각 레벨에 노드 추가
6. 결과 출력

---

1. 입력받기 

        // 입력값 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 결과값 출력 
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        

        K = Integer.parseInt(br.readLine()); // 2

        StringTokenizer st = new StringTokenizer(br.readLine()); // 2 1 3

 

2.트리의 총 노드 수 계산

        // 1. 트리 총 노드수 계산
        // 깊이가 K인 완전 이진 트리는 총 2^K - 1개의 노드로 이루어짐
        // k = 2 , 2^2 - 1 = 3개
        size = (int) (Math.pow(2, K) - 1); // 3

 

3.중위 순회 결과 저장

       static int[] num; // 초기 중위 순회 결과 저장
       ...
       
       // num 초기화 // 2 1 3 들어가야함 
        num = new int[size + 1];

        // 2. 중위 순회 결과 저장 [2 , 1, 3]
        int index = 1;
        while(st.hasMoreTokens()){
            num[index++] = Integer.parseInt(st.nextToken());
        }

 

4.레벨별로 노드를 저장할 리스트 초기화

static ArrayList<Integer>[] tree; // 각 레벨별로 노드를 저장할 리스트
...
        // 3. 레벨별로 노드를 저장할 리스트 초기화
        tree = new ArrayList[K + 1]; // 레벨 1, 레벨 2 ..
        for(int i = 0; i <= K; i++) {
            tree[i] = new ArrayList<>();
        }

[K + 1]인 이유? -> 트리의 레벨은 1부터 K까지 존재하므로, 0번째 인덱스를 사용하지 않고,  1번째 인덱스부터 K번째 인덱스까지 사용하기 위해 배열의 크기를 K + 1로 설정

 

5. 중위 순회 결과를 이용해 트리 구성 및 각 레벨에 노드 추가

        // 4. 중위 순회 결과를 이용해 트리 구성 및 각 레벨에 노드 추가
        search(1,1, size);
        ....
        
    // 중위 순회 특성을 이용하여 트리를 구성하고 각 레벨에 맞는 빌딩 값들을 저장
    private static void search(int depth, int start, int end) {
        int mid = (start + end) / 2; // 현재 서브트리의 루트 노드 위치(중간 지점)
        tree[depth].add(num[mid]); // 현재 레벨에 루트 노드 추가 

        // 단말 노드(자식이 없는 노드)일 때 재귀 종료
        if(depth == K) return;

        // 왼쪽 서브트리 구성
        search(depth + 1, start, mid - 1);

        // 오른쪽 서브트리 구성
        search(depth + 1, mid + 1, end);
    }

 

ex) 깊이 3인 완전 이진 트리의 중위 순회 결과가 1 2 3 4 5 6 7인 경우

1. 처음 호출: search(1, 1, 7):
   • mid = 4: tree[1]에 num[4] (즉, 4)를 추가합니다.
2. 왼쪽 서브트리: search(2, 1, 3):
   • mid = 2: tree[2]에 num[2] (즉, 2)를 추가합니다.
3. 왼쪽 서브트리: search(3, 1, 1):
   • mid = 1: tree[3]에 num[1] (즉, 1)를 추가합니다.
4. 오른쪽 서브트리: search(3, 3, 3):
   • mid = 3: tree[3]에 num[3] (즉, 3)를 추가합니다.
5. 오른쪽 서브트리: search(2, 5, 7):
   • mid = 6: tree[2]에 num[6] (즉, 6)를 추가합니다.
6. 왼쪽 서브트리: search(3, 5, 5):
   • mid = 5: tree[3]에 num[5] (즉, 5)를 추가합니다.
7. 오른쪽 서브트리: search(3, 7, 7):
   • mid = 7: tree[3]에 num[7] (즉, 7)를 추가합니다.

6.결과 출력

		// 각 레벨에 있는 빌딩 정보 bw에 저장
        for(int i = 1; i <= K; i++) {
            for(int j = 0; j < tree[i].size(); j++) {
                bw.write(tree[i].get(j) + " ");
            }
            bw.newLine();
        }

        // 결과 출력
        bw.flush();

        bw.close();
        br.close();