[Lv_3] 표현 가능한 이진트리

🔍 아이디어

✔️ 주어진 숫자를 이진수로 변환하고, 이진수를 이진트리로 표현할 경우의 최대 깊이를 구한다.
✔️ 최대 깊이를 통해 최대 노드 개수를 계산하고, 부족한 노드만큼 _!0!_ 을 붙여 완전포화이진트리로 만든다.
✔️ 중앙 인덱스 값을 체크하면서 완전포화이진트리 검증한다.

import java.util.*;

class Solution {
	// 정답 배열
    static int[] ans = null;
    
    public int[] solution(long[] numbers) {
        ans = new int[numbers.length];
        Arrays.fill(ans, 1);
        
        for (int i = 0; i < numbers.length; i++) {
            String binary = Long.toBinaryString(numbers[i]);
            int depth = getDepth(binary);
            int len = binary.length();
            
            // 계산된 깊이의 최대 길이를 구한다.
            int maxLen = (int) Math.pow(2, depth);
            
            // 이진수의 길이가 주어진 깊이 최대 길이와 같다면 2를 추가로 곱한다.
            // 완전포화 상태까지 0을 붙여줘야하기 때문이다.
            if (binary.length() == maxLen) {
                maxLen *= 2;
            }
                        
            while (binary.length() < maxLen - 1) {
                binary = "0" + binary;
            }
            
            // 길이가 2의 짝수이거나, 이진수의 값이 0이면 생략
            if (binary.length() % 2 == 0 || binary.equals("0")) {
                ans[i] = 0;
                continue;
            }
            
            checkBinary(binary, i);
        }
        
        return ans;
    }
    
    void checkBinary(String binary, int index) {
    	// 체크 이진수의 길이가 1이면 종료
        // 현재 index 단계의 검증이 종료되었으면 종료
        if (binary.length() == 1 || ans[index] == 0)  {
            return;
        }
        
        char c = pick(binary);
        int center = binary.length() / 2;
        
        String prevStr = binary.substring(0, center);
        String nextStr = binary.substring(center + 1);
        
        // 주어진 이진수의 중앙 인덱스 단어를 찾고 0일 경우 자손 노드 확인
        // 둘 중 하나라도 값이 1이면 끊어진 이진트리로 0 처리하고 종료
        if (c == '0') {
            char prev = pick(prevStr);
            char next = pick(nextStr);
            
            if (prev == '1' || next == '1') {
                ans[index] = 0;
                return;
            }
        }
        
        checkBinary(prevStr, index);
        checkBinary(nextStr, index);
    }
    
    char pick(String binary) {
        int center = (binary.length() / 2);
        return binary.charAt(center);
    }
    
    int getDepth(String binary) {
        return (int) Math.ceil(Math.log10(binary.length()) / Math.log10(2));
    }
}

✔️링크: 코딩테스트 연습 - 표현 가능한 이진트리 | 프로그래머스 스쿨 (programmers.co.kr)