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

📌 Problem

주어진 배열에 있는 long 타입 정수들을 포화 이진 트리로 나타낼 수 있는지를 확인하면 된다. 정수를 이진수로 나타냈을 때 1은 node가 있는 위치이며 0은 포화 이진 트리를 만들기 위해 기존 트리에 0이라는 더미 node를 붙인 곳이다. 또한 이진수는 트리를 왼쪽부터 읽은 값이다.

📌 Solution

우선 주어진 정수를 이진수로 변환해야 한다. 이때 이진 트리의 높이에 따라 이진수의 왼쪽에 0을 붙여야 한다. 예를 들어 63이라는 정수를 이진수로 바꾸면 111111이다. 이진수의 길이에 맞는 트리의 최소 높이는 3이다. 높이가 3인 포화 이진 트리의 노드 수는 7이지만 이진수 111111은 길이가 6이기 때문에 그 차이인 1만큼 0을 왼쪽에 붙여서 0111111을 만든다.

private int convert(long number) {
    String bits = Long.toBinaryString(number);
    int h = 0;
    while ((int) Math.pow(2, h) - 1 < bits.length()) h++;
    while ((int) Math.pow(2, h) - 1 != bits.length()) bits = 0 + bits;
    int height = (int) (Math.log(bits.length() + 1) / Math.log(2));
    return check(bits, 0, bits.length() - 1, height) ? 1 : 0;
}

이 때부터는 포화 이진 트리인지를 확인하면 된다. 이진수의 가운데 값이 root이다. root 값이 0이면 왼쪽과 오른쪽 node의 값이 1이 되어서는 안된다. 이때 leftIndex = (from + rootIndex - 1) / 2, rightIndex = (rootIndex + 1 + to) / 2이다. from과 to는 sub tree의 index 범위이다.

private boolean check(String bits, int from, int to, int height) {
    if (height == 1) return true;
    int root = (from + to) / 2;
    int leftChildIndex = (from + root - 1) / 2;
    int rightChildIndex = (root + 1 + to) / 2;
    if (bits.charAt(root) == '0') {
        if (bits.charAt(leftChildIndex) == '1') return false;
        if (bits.charAt(rightChildIndex) == '1') return false;
    }
    height--;
    return check(bits, from, root - 1, height) && check(bits, root + 1, to, height);
}

📌 Code

public int[] solution(long[] numbers) {
    return Arrays.stream(numbers).mapToInt(this::convert).toArray();
}

private int convert(long number) {
    String bits = Long.toBinaryString(number);
    int h = 0;
    while ((int) Math.pow(2, h) - 1 < bits.length()) h++;
    while ((int) Math.pow(2, h) - 1 != bits.length()) bits = 0 + bits;
    int height = (int) (Math.log(bits.length() + 1) / Math.log(2));
    return check(bits, 0, bits.length() - 1, height) ? 1 : 0;
}

private boolean check(String bits, int from, int to, int height) {
    if (height == 1) return true;
    int root = (from + to) / 2;
    int leftChildIndex = (from + root - 1) / 2;
    int rightChildIndex = (root + 1 + to) / 2;
    if (bits.charAt(root) == '0') {
        if (bits.charAt(leftChildIndex) == '1') return false;
        if (bits.charAt(rightChildIndex) == '1') return false;
    }
    height--;
    return check(bits, from, root - 1, height) && check(bits, root + 1, to, height);
}