문제

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

최초 풀이

1) 주어진 num을 이진수로 변환
2) 포화 이진트리가 될수 있는 이진수로 만들기
3) 변환된 이진수를 Tree로 변환
4) Tree를 순회하여 표현이 가능한지 Check하는 함수 실행

이진수를 이진트리로 직접 변환하여, 트리를 순회하는 방식으로 구현하였다.

LeetCode에서 주어진 TreeNode를 사용해 문제를 푸는데에 익숙해지다보니, 굳이 쓸데없는 과정을 추가하고 말았다.

function solution(numbers) {
    let answer = [];
    let result = [];
    
    // 이진트리를 위한 Node
    function TreeNode(val, left, right) {
        this.val = val;
        this.left = left ? left : null;
        this.right = right ? right : null;
    }
    
    // 이진수를 이진트리로 변환
    function setBST (arr) {
        if(!arr.length) return;
    
        let mid = Math.floor(arr.length/2);

        const node = new TreeNode(arr[mid])
        node.left = setBST(arr.slice(0,mid))
        node.right = setBST(arr.slice(mid+1))
        
        return node;
    }
    
    // Check하는 함수
    function checkTree(node, parent) {
        if(!node) return true;

        if(parent == 0) {
            if(node.val == 1) return false;
        }
        
        if(node.val == 0) parent = 0;
        
        if(!checkTree(node.left, parent)) return false;
        if(!checkTree(node.right, parent)) return false;
        
        return true;
    }
    const temp = setBST([0,1,1,1,0,1,0])

    
    for(let num of numbers){
        let biNum = num.toString(2);
        const h = Math.ceil(Math.log2(biNum.length + 1));
        const temp = '0'.repeat(2 ** h  - 1 - biNum.length)
        biNum = temp + biNum

        const biNumArr = biNum.split("")
        const root = setBST(biNumArr);
        if(checkTree(root, 1)) result.push(1); 
        else result.push(0)     
    }
    return result;
}

개선된 코드

문자열을 그냥 바로 순회하면서 Possible함수 실행.

Bit manipulation에 좀 더 익숙해지면 좋을 것 같다.

또한 기본적인 String method들도 복습하는 계기가 된듯.

// numbers를 순회
// num을 이진수로 변환
// 이진수를 포화이진트리가 될수있게 변환 (pad())
// 변환된 이진수에 check() 실행

function ceilLog2(n) {
    return Math.ceil(Math.log2(n))
}

function possible(n) {
    if(n.length <= 1)
        return true
    const mid = n.length >> 2
    
    const leftChild = n.slice(0,mid);
    const rightChild = n.slice(mid+1);

    if(n[mid] == '1') {
        return possible(leftChild) && possible(rightChild)
    } else {
        return !(+leftChild) && !(+rightChild)
    }
}

function pad(n) {
    return n.padStart(2**ceilLog2(n.length+1) - 1, '0')
}

function solution(numbers) {
    return numbers.map(number => {
        number = number.toString(2);
        number = pad(number);
        return Number(possible(number))
    })
}