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

🎨 문제

프로그래머스

📘 풀이

이 문제는 분할 정복으로 풀 수 있습니다. 루트 노드를 기준으로 왼쪽 서브 트리와 오른쪽 서브 트리가 포화 이진 트리인지 확인하면 됩니다. 우선 포화 이진 트리에 대해 간단히 알아보겠습니다.

포화 이진 트리

포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖습니다.

포화 이진트리는 레벨에 따라 노드의 개수가 정해져 있습니다. 루트 노드의 레벨을 0 레벨이라 했을 때 n 레벨의 노드의 개수는 2의 n승이 됩니다. 따라서 n레벨의 포화 이진 트리의 노드 개수는 2의 n승 - 1입니다. 이 부분이 10진수를 2진수로 변환할 때 문제를 일으킵니다.

진수 변환

문제는 10진수가 이진트리가 되는지 확인하는 것입니다. 이를 위해 다음과 같은 방법으로 10진수를 2진수로 변환했습니다.

 

Long.toBinaryString(number);

 

10진수를 2진수로 변환하는데는 성공했지만 아직 한 단계 더 남았습니다.

포화 이진 트리로 만들기

위의 방식으로 2진수를 구하면 2진수가 포화 이진 트리가 되지 않을 수 있습니다. 58을 예로 들겠습니다. 58은 2진수로 "111010"입니다. 이를 트리로 만들면 다음과 같습니다.

 

111010

 

맨 앞에 0이 빠져서 포화 이진트리가 되지 못합니다. 따라서 저희가 원하는 2진수는 "0111010"입니다.

 

0111010

진수 변환으로는 앞에 0이 얼마나 빠졌는지 알 수 없기 때문에 다른 방법을 사용해야 합니다. 이때 포화 이진 트리의 노드의 개수를 활용하면 됩니다.

 

레벨(n)마다 2의 n승 개의 노드가 추가되므로 이를 통해 필요한 0의 개수를 구합니다. 진수 변환으로 구한 binary에 추가로 필요한 0을 붙여 반환합니다.

 

private String getFullBinary(String binary) {
    int length = binary.length();
    int nodeCount = 1;
    int level = 1;
    while (length > nodeCount) {
        level *= 2;
        nodeCount += level;
    }

    int offset = nodeCount - length;	// 앞에 추가해야할 0의 개수
    return "0".repeat(offset) + binary;
}

분할 정복

이제 주어진 포화 이진 트리에서 0을 뺏을 때 이진 트리가 되는지 확인하면 됩니다. 즉, 포화 이진트리에서 0인 노드의 서브트리는 모두 0이여야 합니다. 

 

private boolean isBinaryTree(String binary) {
    int len = binary.length();
    if (binary.length() == 0) return true;	// 리프 노드에서 isBinaryTree()를 호출한 경우

    int root = len / 2;
    String leftSubTree = binary.substring(0, root);
    String rightSubTree = binary.substring(root + 1);

    if (binary.charAt(root) == '0') {	// 루트 노드가 0이라면 서브 트리도 모두 0
        return isZeroTree(binary.substring(0, root)) && isZeroTree(binary.substring(root + 1));
    }

	// 루트 노드가 1이라면 서브 트리 검사
    return isBinaryTree(leftSubTree) && isBinaryTree(rightSubTree);
}

 

private boolean isZeroTree(String binary) {
    int len = binary.length();
    if (binary.length() == 0) return true;

    int root = len / 2;
    String leftSubTree = binary.substring(0, root);
    String rightSubTree = binary.substring(root + 1);

    if (binary.charAt(root) == '1') {
        return false;
    }

    return isZeroTree(leftSubTree) && isZeroTree(rightSubTree);
}

📗 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] solution(long[] numbers) {
        List<Integer> answer = new ArrayList<>();

        for (long number : numbers) {
            if (isBinaryTree(number)) {
                answer.add(1);
            } else {
                answer.add(0);
            }
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

    private boolean isBinaryTree(long number) {
        String binary = Long.toBinaryString(number);
        String fullBinary = getFullBinary(binary);
        int len = fullBinary.length();

        int root = len / 2;
        String leftSubTree = fullBinary.substring(0, root);
        String rightSubTree = fullBinary.substring(root + 1);

        if (fullBinary.charAt(root) == '0') {
            return false;
        }

        return isBinaryTree(leftSubTree) && isBinaryTree(rightSubTree);
    }

    private String getFullBinary(String binary) {

        int length = binary.length();
        int nodeCount = 1;
        int level = 1;
        while (length > nodeCount) {
            level *= 2;
            nodeCount += level;
        }

        int offset = nodeCount - length;
        return "0".repeat(offset) + binary;
    }

    private boolean isBinaryTree(String binary) {
        int len = binary.length();
        if (binary.length() == 0) return true;

        int root = len / 2;
        String leftSubTree = binary.substring(0, root);
        String rightSubTree = binary.substring(root + 1);

        if (binary.charAt(root) == '0') {
            return isZeroTree(leftSubTree) && isZeroTree(rightSubTree);
        }

        return isBinaryTree(leftSubTree) && isBinaryTree(rightSubTree);
    }

    private boolean isZeroTree(String binary) {
        int len = binary.length();
        if (binary.length() == 0) return true;

        int root = len / 2;
        String leftSubTree = binary.substring(0, root);
        String rightSubTree = binary.substring(root + 1);

        if (binary.charAt(root) == '1') {
            return false;
        }

        return isZeroTree(leftSubTree) && isZeroTree(rightSubTree);
    }
}