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

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

프로그래머스

 

풀이)

이진트리가 표현 가능하려면

부모 노드가 0일 때 자식 노드도 0이어야 한다

= 부모 노드가 0일 때 자식 노드가 1이라면 -> 표현 불가!

 

나머지는 주석을 참고

 

function solution(numbers) {
    var answer = [];
    
    for (const number of numbers) {
        // 1. 이진수로 변환
        let bNumber = number.toString(2);
        
        // 2. 앞에 0을 붙일 길이 구하기
        // 이유 : 포화 이진트리로 만들기 위해
        // 예시 1, 111, 1111111
        let len = bNumber.length;
        let depth = 1;
        
        while (true) {
            if (2**depth - 1 >= len) {
                len = 2**depth - 1;
                break;
            }
            
            depth++;
        }
        
        // 3. 문자열 포화 이진트리로 만들어주기
        // 주의 : padStart 메서드는 원본 문자열을 변경해주지 않는다
        bNumber = bNumber.padStart(len, '0');
        
        let isPossible = true;
        
        // 4. dfs로 맞는지 확인
        // 부모가 0이면 자식도 무조건 0
        const dfs = (start, end) => {
            if (start >= end) return;
            if (!isPossible) return;
            
            const mid = Math.floor((start + end) / 2);
            
            if (bNumber[mid] === '0') {
                // 주의! - 직계 자식을 확인
                const left = Math.floor((start + mid - 1) / 2);
                const right = Math.floor((mid + 1 + end) / 2);
                
                if (bNumber[left] === '1' || bNumber[right] === '1') {
                    isPossible = false;
                    return;
                }
            }
            
            dfs(start, mid - 1);
            dfs(mid + 1, end);
        }
        
        dfs(0, len-1);
        
        answer.push(isPossible ? 1 : 0);
    }
    
    return answer;
}