표현 가능한 이진트리

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

프로그래머스

이진 트리로 구성 가능한지 판단하는 문제이다.

이진 트리를 구성 하는 룰에 따라 LeafNode ( 자식이 없는 마지막 노드 ) 가 있다면,
그 부모의 노드도 있어야 하기에 이진법으로 변환한 값을 보고 부모의 여부를 판단할 수 있다.

 

입력된 값을 이진법으로 변환한 뒤 인덱싱을 위해 암묵적 ( 문제의 점선 ) 노드를 모두 생성한 뒤
( white space )

왼쪽, 오른쪽의 노드가 있으면서 부모가 없는 경우를 실패하는 경우로 간주하여 문제를 풀 수 있다.

 

큰 고민 없이 N^2 시간 복잡도로 풀 수 있다.

function solution(numbers) {
    function getAnswer(number) {
        // decimal -> binary
        var numStr = number.toString(2);
        var numStrLength = numStr.length;

        // get maximum length of binary digit
        var maxLeafNumIdx = 1;
        var maxLeafNum = (1 << maxLeafNumIdx) - 1;
        while(maxLeafNum < numStrLength) {
            maxLeafNumIdx += 1;
            maxLeafNum = (1 << maxLeafNumIdx) - 1;
        }
        
        // fill white space ( 0 )
        for (var i = numStrLength; i < maxLeafNum; i++) {
            numStr = '0' + numStr;
        }

        // step below to top
        for (var i = 1; i < maxLeafNumIdx; i++) {
            for (var j = (1 << (i - 1)); j < maxLeafNum; j += (1 << (i + 1))) {
                var leftIdx = j;
                var rightIdx = j + (1 << i);
                
                // left or right is '1'. there's parent must be '1'.
                // * add '-1' when index to array
                if ((numStr[leftIdx - 1] === '1' || numStr[rightIdx - 1] === '1') && numStr[((leftIdx + rightIdx) / 2) - 1] === '0') {
                    return 0;
                }
            }
        }

        
        return 1;
    }

    return numbers.map(getAnswer);
}