[Programmers] 표현 가능한 이진트리 (Java)

1.  문제 링크

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

2.  문제

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

이진트리를 수로 표현하는 방법은 다음과 같습니다.

• 1. 이진수를 저장할 빈 문자열을 생성합니다.
  2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
  3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
  4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
  5. 문자열에 저장된 이진수를 십진수로 변환합니다.

이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.
다음은 이진트리를 수로 표현하는 예시입니다.
주어진 이진트리는 다음과 같습니다.


주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.


노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.
당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.
이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

3.  제한사항

• 1 ≤ numbers의 길이 ≤ 10,000
  • 1 ≤ numbers의 원소 ≤ 1015

입출력 예

4.  소스코드

class Solution {
    static final long SIZE = (long)10e15;
    static int maxLen, maxExponent;
    public static int[] solution(long[] numbers) {
        findMaxSize();
        int[] answer = new int[numbers.length];
        for(int idx = 0; idx < numbers.length; idx++) {
            String binary = makeBinary(numbers[idx]);
            boolean[] isOne = new boolean[binary.length()];
            findOnePlace(binary, isOne);
            if(isBinaryTree(binary, isOne)) answer[idx] = 1;
            else answer[idx] = 0;
        }
        return answer;
    }

    static boolean isBinaryTree(String binary, boolean[] isOne) {
        if(binary.length() == 1) return true;
        int center = binary.length() / 2;
        if(binary.charAt(center) == '0') {
            boolean flag = true;
            for(int idx = 0; idx < binary.length(); idx++) {
                if(center == idx) continue;
                if(binary.charAt(idx) == '1') {
                    flag = false;
                    break;
                }
            }
            if(!flag) return false;
        }
        String left = binary.substring(0, center);
        String right = binary.substring(center + 1);
        boolean leftTree = isBinaryTree(left, isOne);
        if(!leftTree) return false;
        boolean rightTree = isBinaryTree(right, isOne);
        if(!rightTree) return false;
        return true;
    }

    static void findOnePlace(String binary, boolean[] isOne) {
        for(int idx = 0; idx < binary.length(); idx++) {
            if(binary.charAt(idx) == '1') isOne[idx] = true;
        }
    }

    static String makeBinary(long number) {
        long copy = number;
        StringBuilder sb = new StringBuilder();
        while(number > 0) {
            long remainder = number % 2;
            sb.insert(0, remainder);
            number /= 2;
        }
        int len = 0;
        for(int exponent = 0; len <= maxLen; exponent++) {
            len += (int)Math.pow(2, exponent);
            if(sb.length() < len) {
                int sbLen = sb.length();
                for(int add = 0; add < len - sbLen; add++) {
                    sb.insert(0, 0);
                }
                break;
            } else if(sb.length() == len) {
                break;
            }
        }
        return sb.toString();
    }

    static void findMaxSize() {
        maxLen = (int)Math.log(SIZE) + 1;
        maxExponent = (int)Math.log(maxLen) + 1;
    }
}

5.  접근

• 어떠한 10진수 수 N을 2진수 K로 변경할 때의 2진수의 길이는 N < $2^L$인 L들 중에서 가장 작은 수와 같습니다. 즉, 해당 수를 log를 취한 후에 1을 더한 것과 같습니다.
• 이를 이용하여 N의 최대 수가 $10^{15}$이기 때문에 위 방법을 이용하여 2진수의 최대 길이를 구합니다.
• 주어진 수를 2진수로 변경합니다.
  • 주어진 수를 2로 나눠가며 나머지를 이용하여 2진수로 변경합니다.
  • 그러나 이후 이를 포화 이진트리로 변경해야하기 때문에 변경한 2진수의 길이와 2의 거듭제곱과 맞지 않는다면 그에 맞게 앞에 0을 추가해줍니다.
• 이렇게 구한 2진수에서 1이 위치하는 곳이 어디인지 나타내는 isOne 배열을 생성하고 1이 위치하는 곳을 찾아 true로 표시합니다.
• 구한 2진수가 포화 이진트리로 변경 가능한지 확인합니다.
  • 주어진 2진수를 가운데 루트를 제외한 반씩 나누어 왼쪽과 오른쪽 각 서브트리가 생성 가능한지 확인합니다.
  • 우선 루트를 확인하고 만약 루트가 0이라면, 주어진 2진수에서 1이 있는지 확인합니다.
  • 만약 1이 있다면 해당 서브트리에서는 트리를 생성할 수 없기 때문에 해당 수는 포화 이진트리로 변경이 불가능합니다.
  • 만약 1이 없다면 그 루트는 전체 포화 이진트리에서 리프에 해당하는 부분이 되므로 이후 다른 서브트리들을 확인합니다.
  • 위와 같은 방식으로 모든 서브트리들을 확인해 만약 모든 서브트리가 생성이 가능하다면 해당 수는 포화 이진트리로 변경이 가능합니다.