[백준] 알고리즘 분류(트리,JAVA)9934번, 완전 이진 트리

문제 링크

9934번: 완전 이진 트리

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 탐색하는 방법은 중위 순회(Left → Root → Right)입니다.

2. 각 레벨에 존재하는 빌딩의 번호들을 순서대로 출력합니다.

3. 주어지는 트리는 항상 완전 이진 트리입니다.

4. 완전 이진 트리에 존재하는 빌딩은 2ⁿ - 1입니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 빌딩의 정보를 저장합니다.

 

2. 중위 순회에 특징을 이용하여 왼쪽 빌딩과 오른쪽으로 나누어서 레벨에 맞게 빌딩을 저장합니다.

 

3. 각 층에 빌딩들을 순서에 맞게 결과로 출력합니다.

 

중위 순회 특징 이용.

 

2 - 1 - 3

가운데 있는 값 : Root

 

가운데에서 왼쪽 : Left

 

가운데에서 오른쪽  : Right

 

※각 Left, Right로 나뉠 때마다 레벨이 증가됩니다.

 

(1 - 6 - 4) - 3 - (5 - 2 - 7)

3 : Level 1

(1 - 6 - 4) : Level 2

(5 - 2 - 7) : Level 2

 

1 - 6 - 4

6 : Level 2

1 : Level 3

4 : Level 3

5 - 2 - 7

2 : Level 2

5 : Level 3

7 : Level 3

예제입력 1.

 

1. 입력된 빌딩의 정보를 저장합니다.

 

K : 2

 

2 - 1 - 3

 

2. 중위 순회에 특징을 이용하여 왼쪽 빌딩과 오른쪽으로 나누어서 레벨에 맞게 빌딩을 저장합니다.

 

2 - 1 - 3

1 : Level 1

2 : Level 2

3 : Level 2

 

 

3. 각 층에 빌딩들을 순서에 맞게 결과로 출력합니다.

 

Level 1 : 1

Level 2 : 2 3

결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리 탐색의 정보를 띄어쓰기 기준 나누었습니다.
• search함수를 통해 각 레벨에 빌딩의 정보들을 저장하였습니다.
• 각 레벨에 저장된 빌딩들을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 중위 탐색의 특징을 각 레벨의 빌딩의 정보들을 저장합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Main {
    static int K, size;
    static int[] num;
    static ArrayList<Integer>[] tree;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        K = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        size = (int)(Math.pow(2, K) - 1);
        tree = new ArrayList[K+1];
        num = new int[size+1];
        for(int i=0;i<=K;i++)
            tree[i] = new ArrayList<>();
        int index = 1;
        //중위 순회 탐색 정보 배열에 저장
        while(st.hasMoreTokens())
            num[index++] = Integer.parseInt(st.nextToken());
        search(1, 1, size);		//중위 순회 특성 이용한 Left, Right 나누기
        //각 층에 빌딩 정보 BufferedWriter 저장
        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();
    }
    //중위 순회 특성 이용한 레벨에 맞는 빌딩 값들 저장 함수
    static void search(int depth, int start, int end){
        int mid = (start + end)/2;		//Root
        tree[depth].add(num[mid]);
        if(depth == K)		//단말 노드일 때
            return;
        search(depth+1, start, mid-1);	//Left
        search(depth+1, mid+1, end);	//Right
    }
}