프로그래머스 - 표현 가능한 이진트리 (JavaScript)

생각해보기

• 포화 이진 트리는 노드의 개수가 2^n - 1개이다.
• 더미 노드는 주어진 수를 변경하면 안되므로 이진수로 변환된 문자열의 앞에 추가된다.
• 부모 노드가 0인데 자식 노드가 1인 경우, 이진 트리가 될 수 없다.
• 부모 노드와 자식 노드가 모두 0인 경우는 가능

 

더미 노드의 개수 파악하기

더미 노드의 개수를 찾는 과정을 반복한다. 이를 통해 규칙성을 파악하고 식으로 나타내보자.

주어진 수	1	2	3	4	5	6	7	8	9
A	1	10	11	100	101	110	111	1000	1001
B	1	2	2	3	3	3	3	4	4
C	1	10	10	11	11	11	11	100	100
D	1	2	2	2	2	2	2	3	3

A : 주어진 수에 대한 이진수 변환

B : A의 길이

C : B에 대한 이진수 변환

D : C의 길이

 

위의 표처럼 2번의 이진수 변환을 통해 주어진 수가 2, 3일 때와 4~7일 때 같은 식을 적용할 수 있게 된다. 포화 이진 트리를 만족하기 위해 노드의 개수는 2^D - 1개가 되어야 한다. 따라서 필요한 더미 노드의 개수는 (2^D - 1) - B개이다.

 

이진 트리 확인하기

포화 이진 트리 형태의 문자열에서 루트 노드는 첫 번째 문자의 인덱스(start)와 마지막 문자의 인덱스(end)의 중간값인 인덱스(mid)를 가진다. 루트 노드의 왼쪽 자식 노드는 (start + (mid - 1)) // 2의 인덱스를 가진다. 마찬가지로 루트 노드의 오른쪽 자식 노드는 ((mid + 1) + end) // 2의 인덱스를 가진다. 이 과정을 반복하여(해당 함수를 재귀적으로 호출) 서브 트리들을 탐색할 수 있다.

 

풀이

function solution(numbers) {
    var answer = [];
    
    const isBinaryTree = (tree, start, end) => {
        if (start == end) return true;
        
        let mid = Math.floor((start + end) / 2);
        let leftChild = Math.floor((start + mid - 1) / 2);
        let rightChild = Math.floor((mid + 1 + end) / 2);
        
        if (tree[mid] === '0' && (tree[leftChild] === '1' || tree[rightChild] === '1')) {
            return false;
            
        }
        return isBinaryTree(tree, start, mid - 1) && isBinaryTree(tree, mid + 1, end);
    };
    
    for (let i = 0; i < numbers.length; i++) {
        let binaryNum = numbers[i].toString(2);
        let binaryNumLength = binaryNum.length;
        let n = binaryNumLength.toString(2).length;
        let dummy = (2**n - 1) - binaryNumLength;
        let fullBinary = '0'.repeat(dummy) + binaryNum;
        
        if (isBinaryTree(fullBinary, 0, fullBinary.length - 1)) {
            answer.push(1);
        }
        else {
            answer.push(0);
        }
    }
    return answer;
}