[프로그래머스 JAVA] Lv.3 표현 가능한 이진트리

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

프로그래머스

 

문제 한 줄 요약

정수 n을 이진수로 보고, 길이를 2^h-1로 패딩한 뒤 중앙을 루트로 분할·검사한다. 규칙은 루트가 0이면 자식 서브트리(좌/우)의 루트가 1일 수 없다.

 

접근

• Long.toBinaryString(n) → 왼쪽 0 패딩으로 길이를 2^h-1에 맞춤
• 문자열을 중위 순회 결과로 간주: 중앙 = 루트, 좌/우 = 서브트리
• 루트가 0일 때 좌/우 서브트리의 루트가 1이면 불가, 아니면 재귀 진행

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i = 0; i < numbers.length; i++){
            long number = numbers[i];
            String binary = Long.toBinaryString(number);
            String fullBinary = pad(binary);
            if(check(fullBinary)) answer[i] = 1;
            else answer[i] = 0;
        }
        
        return answer;
    }

    // 길이를 2^h - 1로 맞추는 패딩
    public static String pad(String s){
        int size = 1;
        int len = s.length();
        while(size - 1 < len) size *= 2;
        int fullLen = size - 1;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < fullLen - len; i++){
            sb.append("0");
        }
        sb.append(s);
        return sb.toString();
    }

    // 루트가 0이면 좌/우 서브트리의 루트가 1이면 불가
    public static boolean check(String s){
        int n = s.length();
        if(n <= 1) return true;
        
        int mid = (n - 1) / 2;
        char root = s.charAt(mid);
        
        String left = s.substring(0, mid);
        String right = s.substring(mid + 1);
        
        if(root == '0'){
            char lroot = left.charAt((left.length() - 1) / 2);
            char rroot = right.charAt((right.length() - 1) / 2);
            if(lroot == '1' || rroot == '1') return false;
        }
        
        return check(left) && check(right);
    }
}

 

복잡도

• 패딩 및 검사 모두 길이 L에 대해 O(L)
• 각 수에 대해 비트 길이 선형

 

회고

• 핵심은 패딩으로 중앙=루트가 되게 만드는 것과, 부모 0 → 자식 루트 1 금지를 레벨별로 검사하는 것.
• 실전에선 이 방식이 가장 직관적이고, 필요하면 substring 없이 인덱스 재귀로 미세 최적화하면 된다.