[프로그래머스/Java] 표현 가능한 이진트리 (2023 카카오 블라인드 채용 기출)

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

프로그래머스

고찰 과정

주어진 정수를 올바른 포화 이진트리로 만들 수 있는지 확인하기 위해서 다음과 같은 과정을 고찰하였습니다.

• number를 이진수로 변환하기
• 이진수가 포화 이진 트리 자릿수만큼 존재하는지 확인해주기
  -> 포화 이진트리 상태일 때의 노드 개수는 항상 홀수이므로 이진수 자릿수가 짝수개라면 앞에 0을 붙여주면서 홀수개로 만들어줍니다.
• 자릿수가 홀수인 이진수를 바탕으로 해당 이진수가 올바른 포화 이진 트리로 만들 수 있는지 확인하기
  -> 문제에 의해서 이진수에서 중앙에 있는 값은 루트 노드가 되므로 재귀적으로 왼쪽 서브트리와 오른쪽 서브 트리로 나누며 올바른 포화 이진트리인지 계속적으로 확인해줍니다.
  -> 올바른 포화 이진트리의 기준은 더미 데이터(0)를 루트 노드로 취급하는 자식 데이터(1)가 존재하는지 아닌지로 판단하였습니다.
  -> 만약 실제 자식 데이터가 존재한다면 해당 이진수는 올바른 포화 이진트리가 아닙니다.
• 결과에 따라서 적절한 answer 배열을 만들기

 

예를 들어서 "0101101" 이진수가 있다고 가정을 해봅시다. 이 이진수를 문제에 따라 트리로 나타내면 다음과 같습니다.

결론적으로 이 이진트리는 올바른 포화 이진트리가 아닙니다. 왜냐하면 오른쪽 서브트리에서 더미데이터 0번 노드에 대한 자식이 존재하기 때문입니다. 그럼 이걸 어떻게 판별하는지 설명하겠습니다.

• 먼저 이진수 "0101101"에서 중앙에 인덱스의 값이 루트 노드이므로 1임을 확인합니다. 확인이 되었으면 왼쪽 서브트리부터 살펴보기 위해서 이진수에서 0번부터 2번인덱스까지 잘라서 재귀적으로 확인합니다.
• 새로운 이진수 "010"(왼쪽 서브트리)에서 루트 노드는 1번 인덱스인 1이므로 이는 더미데이터가 아니기에 계속적으로 확인합니다. 결론적으로 왼쪽 서브트리인 "010"은 올바른 포화 이진트리 상태가 됩니다.
• 다시 "0101101" 로 돌아와서 이번엔 오른쪽 서브트리(4번 인덱스부터 6번 인덱스)를 확인합니다.
  "101" 이진수에서 중앙값은 1번 인덱스인 0인데 이는 더미데이터이고 양쪽 다 자식을 가지고 있으므로 이는 올바른 포화 이진트리 상태가 아니므로 결론적으로는 올바른 포화 이진상태가 아님에 도달하게 됩니다.
  

 

이러한 과정들을 단계적으로 생각하여 코드를 구현하였습니다.

 

---

코드

class Solution {
    
    private static final int VALID = 1;
    private static final int INVALID = 0;
    
    public int[] solution(long[] numbers) {
        int len = numbers.length;
        int[] answer = new int[len];

        for (int i = 0; i < len; ++i) {
            String binary = Long.toBinaryString(numbers[i]);
            
            int depth = (int) Math.ceil(Math.log(binary.length() + 1) / Math.log(2));
            int fullBinaryLength = (int) Math.pow(2, depth) - 1;
            
            binary = String.format("%" + fullBinaryLength + "s", binary).replace(' ', '0');
            
            if (isFullBinaryTree(binary, 0, fullBinaryLength - 1)) {
                answer[i] = VALID;
            } else {
                answer[i] = INVALID;
            }
        }
        
        return answer;
    }
    
    private boolean isFullBinaryTree(final String binary, int left, int right) {
        if (left > right) {
            return true;
        }
        
        int mid = (left + right) / 2;
        
        if (binary.charAt(mid) == '0' && binary.substring(left, right + 1).contains("1")) {
            return false;
        } 

        return isFullBinaryTree(binary, left, mid - 1) && isFullBinaryTree(binary, mid + 1, right);
    }
}