[프로그래머스] 2023 KAKAO BLIND - 표현 가능한 이진트리 (자바)

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

프로그래머스

 

---

문제 

 

문제를 이해하는데 조금 어려움이 있었다 

설명에 나와있는 대로 이진트리 -> 이진수 -> 십진수 대로 이해하려해서 조금 헤맸다 

 

결국 배열에 주어진 십진수를 토대로 이진수를 만들고,

1, 0으로 이루어진 해당 문자열을 포화이진트리로 만들었을 때 정상적인 트리가 되는지 에 대한 문제다. 

 

---

풀이

 

단계별로 생각해보면

 

1. 주어진 숫자를 이진수로 변환한다 

 

2. 변환한 이진수를 토대로 이진트리를 만들고, 해당 이진트리가 포화이진트리가 아니라면 (포화이진트리 크기보다 문자열이 적다면) '더미' 라고 하는 노드를 덧붙여 포화이진트리를 생성한다. 

 

높이는 이진수의 길이를 토대로 log를 통해 구할 수 있다. ( 코드 참조 )

포화이진트리의 크기는 2^트리의 높이 - 1 이다. 

 

 

3. 만들어진 이진트리가 정상적인 것인지 판단한다. 

이진트리가 정상적인지 판단하는 기준은 더미 ( = 임의로 붙여준 유령노드, 0을 갖는다 ) 는 실제 자식 (1을 가지는 노드) 을 가질 수 없다. 

 

---

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i = 0; i<numbers.length; i++) {
            String binaryTree = getBinaryTree(numbers[i]);
            if (checkTree(binaryTree)) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }
        return answer;
    }
    
    // 이진수 변환작업, 이진수의 길이가 포화트리보다 작다면 숫자를 변형시키지 않도록 앞에만 0을 붙인다 
    private String getBinaryTree(long number) {
        String binary = Long.toBinaryString(number);
        int height = (int) Math.ceil(Math.log10(binary.length() + 1) / Math.log10(2));
        int size = (int) Math.pow(2, height) - 1;
        
        int dummy = size - binary.length();
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < dummy; i++) {
            sb.append("0");
        }
        
        sb.append(binary);
        return sb.toString();
    }
    
    // 더미노드는 1인 자식을 가질 수 없다. 
    private boolean checkTree(String binaryTree) {
        if (binaryTree.length() <= 1) {
            return true;
        }
        
        String leftTree = binaryTree.substring(0, binaryTree.length() / 2);
        String rightTree = binaryTree.substring(binaryTree.length() / 2 + 1);
        
        
        char root = binaryTree.charAt(binaryTree.length() / 2);
        char left = leftTree.charAt(leftTree.length() / 2);
        char right = rightTree.charAt(rightTree.length() / 2);
        
        if (root == '0' && (left == '1' || right == '1') )
            return false;
        else
            return checkTree(leftTree) && checkTree(rightTree);
    }
}