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

접근 방법

1. 이 문제는 총 세 가지의 소문제로 나눠서 생각하면 좋다
   • 입력받은 십진수 문자열을 이진수 문자열로 변환
   • 포화이진트리를 구현하기 위해 왼쪽에 더미 노드를 패딩(LPAD) 처리
   • 마지막으로 문제 조건을 만족 가능한 포화이진트리인지 판단
2. 십진수를 이진수로 변환할 때 쓰는 보편적인 방법으로 2씩 나누면서 나머지를 문자열로 더해주고 그 결과 값을 뒤집어주는 방식을 사용할 수 있지만... 그냥 시간을 아끼기 위해서 내장 함수인 Long.toBinaryString()을 사용해서 실제 이진 문자열 길이 actualStringLength 값을 구한다.
3. 포화이진트리(CBT)의 특성 중 하나는 깊이 N인 CBT의 노드의 갯수는 N ** 2 - 1라는 점이다. 이 부분은 직접 공책에 이진 트리를 그려보면 쉽게 알 수 있는 사실이다. 그 뜻은 즉, 어떤 depth N을 가진 포화이진트리를 '표현한' 이진 문자열은 N ** 2 - 1의 길이를 가질 수 밖에 없다는 것이다. 따라서 2 ** N - 1 값이 actualStringLength 값보다 크거나 같은 N 중 가장 큰 값을 구한다 (2씩 곱해가면서). 그 다음엔 길이가 2 ** N - 1가 될때까지 문자열의 왼편에 '0'을 LPAD 한다.
4. 전처리가 끝난 포화이진트리 문자열의 중간 값, 양옆의 문자열 이렇게 있을 때, 중간 값이 1인 경우 다시 양옆에 대해서 분할 정복으로 조건이 만족하는지 구한다음 && 연산을 해준다. 중간 값이 0인 경우, 양 옆의 문자열의 구성이 모두 '0'이라면 true, 아니라면 바로 false를 return 한다.

코드

import java.util.Arrays;
import java.lang.Math;

class Solution {
    private static boolean allZeros(String str) {
        for (int i = 0; i < str.length(); i++)
            if (str.charAt(i) != '0')
                return false;
        return true;
    }
    
    private static boolean isPossible(String num) {
        if (num.length() == 1) return true;

        int mid = num.length() / 2;
        String leftNum = num.substring(0, mid);
        String rightNum = num.substring(mid + 1);
            
        if (num.charAt(mid) == '0') {
            if (allZeros(leftNum) && allZeros(rightNum)) return true;
            else return false;
        }

        return isPossible(leftNum) && isPossible(rightNum);
    }

    public static int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            StringBuilder binaryString = new StringBuilder(Long.toBinaryString(numbers[i]));

            int actualStringLength = binaryString.toString().length();
            int depth = 1;
            
            while ((int) Math.pow(2, depth) - 1 < actualStringLength)
                depth++;
            int expectedLength = (int) Math.pow(2, depth) - 1;
            while (binaryString.toString().length() < expectedLength)
                binaryString.insert(0, "0");
            if (isPossible(binaryString.toString())) answer[i] = 1;
        }
        return answer;
    }
}

복기

1. 문자열 길이 관련해서 조건문을 생각해내는 능력을 더 키워야겠다
2. 역시 문제를 푸는 방법은 쉽게 떠올렸으나, 구현 능력이 아직 많이 부족하다