[프로그래머스][분할정복] 표현 가능한 이진트리

     

목차

 

 

문제

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

프로그래머스

 

 

문제 구현 방향

1. 이진수 형태로 바꾸어 준다.

2. 2^n-1 길이가 될때 까지 0을 넣어준다.(완전 이진트리의 길이)

3. 분할 정복을 진행한다. 중간이 0일때 오른쪽, 왼쪽에 하나라도 1이 있으면 잘못된 트리이다.

 

 

코드 구현

function binaryConvert(num) {
    let str = [];
    while (num > 0) {
        str.push(num % 2);
        num = Math.floor(num / 2);
    }
    str = str.reverse();
    let len = str.length;
    let max = 2;
    while(max-1 < len){
        max *=2;
    }
    while(str.length <=max-1){
        str.unshift(0);
    }
    return str;
}

function solution(numbers) {
    const answer = [];
    for (let num of numbers) {
        const str = binaryConvert(num);
        let flag = searching(str);
        answer.push(flag);
    }
    return answer;
}


function searching(str) {
    if (str.length < 3) return 1;
    const mid = Math.floor(str.length / 2);
    const left = str.slice(0, mid);
    const right = str.slice(mid + 1);
    if (
        str[mid] === 0 &&
        (left[Math.floor(left.length / 2)] === 1 ||
            right[Math.floor(right.length / 2)] === 1)
    ) {
        
        return 0;
    }
    return searching(left) && searching(right);
    
}