[2023 KAKAO BLIND RECRUITMENT] 표현 가능한 이진트리

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

프로그래머스

 

처음에는 문제를 이해하기 어려웠는데, 결론은 다음과 같다.

• 포화 이진트리가 되기 위해서는, 이진수의 길이(= 포화이진트리의 노드 수)는 2^n - 1이어야 한다.
  • 포화 이진트리의 노드 수는 다음과 같다. ➡️ 1, 3, 7, 15, ...
• 루트 노드가 0이면 그 아래 자식 노드들은 모두 0이어야 한다.
  • 문제에서 이진트리(1)에 더미노드(0)를 추가하여 포화 이진트리를 만든다고 했다.
  • 따라서 루트 노드가 1이면 자식 노드들은 0 또는 1이 될 수 있지만,
  • 루트 노드가 0이면 해당 루트 노드는 더미 노드라는 의미이고, 더미 노드 아래에는 계속 더미 노드만 추가할 수 있으므로, 루트 노드가 0이면 자식 노드들은 모두 0이어야 한다. 

이 두 결론을 가지고 코드로 구현하면 된다. 

1. 십진수를 이진수로 변환한다.
2. 이진수의 길이가 2^n - 1가 될 때까지 앞에 0을 붙인다.
3. 길이가 완성되면, dfs를 통해 모든 노드를 탐색하며 포화 이진트리인지 확인한다. (루트 노드를 기준으로 왼쪽 트리와 오른쪽 트리를 또 탐색해야 한다. 이 점에서 깊이 우선 탐색인 dfs가 적절하다.

import java.util.*;

class Solution {
    public int[] solution(long[] numbers) {
        
        int[] answer = new int[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            String str = Long.toBinaryString(numbers[i]);
            while (!collectLength(str)) {
                str = "0" + str;
            }
            
            boolean result = dfs(str);
            answer[i] = result ? 1 : 0;
        }
        
        return answer;
    }
    
    public boolean collectLength(String str) {
        int len = str.length() + 1; // len이 2의 제곱이어야 함
        int n = 1;
        while(n < len) {
            n *= 2;
        }
        return len == n;
    }
    
    public boolean dfs(String str) {
        if (str.length() == 1) {
            return true;
        }
        
        int mid = str.length() / 2;
        String leftTree = str.substring(0, mid);
        String rightTree = str.substring(mid + 1);
        
        // 루트 노드가 0이면 왼쪽, 오른쪽 모든 자식 노드도 0이어야 함
        if (str.charAt(mid) == '0') {
            if (leftTree.contains("1") || rightTree.contains("1")) {
                return false;
            }
        }
        
        return dfs(leftTree) && dfs(rightTree);
    }
}