[프로그래머스] 표현 가능한 이진 트리 자바

 

https://school.programmers.co.kr/learn/courses/30/lessons/150367

 

 

분할정복을 사용하는 문제입니다.

 

 

[풀이한 코드]

import java.util.*;

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            answer[i] = getAnswer(numbers[i]);
        }
        return answer;
    }
    
    static int getAnswer(long number) {
        // 1) 십진수 -> 이진수 변환
        String binary = Long.toBinaryString(number);
        
        // 2) 이진수에 더미 노드 채우기
        double size = getSize(binary.length());
        StringBuilder add = new StringBuilder();
        for (int i = binary.length(); i < size; i++) {
            add.append("0");
        }
        binary = add.toString() + binary;
        
        // 3) 만든 트리가 올바른 트리인지 확인하기
        if (isBinaryTree(binary)) {
            return 1;
        }
        return 0;
    }
    
    static int getSize(int length) {
        int h = 1;
        while((int) Math.pow(2, h) - 1 < length) {
            h++;
        }
        return (int) Math.pow(2, h) - 1;
    }
    
    static boolean isBinaryTree(String tree) {
        int len = tree.length();
        if (tree.length() == 0) {
            return true;
        }
        
        int root = len / 2;
        String leftSubTree = tree.substring(0, root);
        String rightSubTree = tree.substring(root + 1);
        if (tree.charAt(root) == '0') {
            return isZeroTree(tree.substring(0, root)) && isZeroTree(tree.substring(root + 1));
        }
        return isBinaryTree(leftSubTree) && isBinaryTree(rightSubTree);
    }
                                                                    
    static boolean isZeroTree(String tree) {
        int len = tree.length();
        if (tree.length() == 0) return true;

        int root = len / 2;
        String leftSubTree = tree.substring(0, root);
        String rightSubTree = tree.substring(root + 1);

        if (tree.charAt(root) == '1') {
            return false;
        }

        return isZeroTree(leftSubTree) && isZeroTree(rightSubTree);
    }
}

 

 

 

[기억하자]

1. 포화 이진 트리의 노드 수: 2 ^ (h + 1)) - 1

- 루트 노드의 레벨을 0이라고 생각했을 때의 공식이다.

- 루트 노드의 레벨을 1이라고 생각하면 2 ^ h - 1 이다.

- 자바로 하면, (int) Math.pow(2, h) - 1 < length 이다. Math.pow() 의 반환값은 double 이기 때문에 (int) 로 강제 형변환할 수 있다.

 

2. Long.toBinaryString(num)

- Integer.toBinaryString(num)도 가능하다.

- 이진수로 변환해준다.

 

3. String.substring(int st, int en)

- string의 s는 대문자가 아니라 소문자이다!

 

4. 트리에서 분할정복 방법

- 트리를 오른쪽 트리와 왼쪽 트리로 나눈다.

- 왼쪽 트리와 오른쪽 트리를 재귀함수로 다시 넣어서 반복한다.

private static boolean dfs(String number) {
    boolean valid = true;

    int mid = (number.length()-1)/2;
    char root = number.charAt(mid);
    String left = number.substring(0,mid);
    String right = number.substring(mid+1,number.length());

    if(root == '0' && (left.charAt((left.length()-1)/2)=='1' || right.charAt((right.length()-1)/2)=='1')){
        return false;
    }
    
    valid = dfs(left);
    if (valid) {
        valid = dfs(right);
    }

    if(left.length() >= 3) {  // 리프노드는 0이어도 상관없기 때문에 길이가 3이상일 때만 탐색
        valid = dfs(left);
        if(valid) {
            valid = dfs(right);
        }
    }
    return valid;
}