프로그래머스: 표현 가능한 이진트리 - javascript(이진트리, 포화이진트리)

문제 출처 

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

프로그래머스

 

문제 풀이 힌트 

이 문제는 주어진 숫자를 이진수로 변환하고, 이를 포화 이진 트리 형태로 만들 수 있는지를 확인하는 문제다. 

 

- 각 숫자를 이진수로 변환한 후, 필요한 더미 노드를 추가하여 포화 이진 트리 형태로 만든다. 

- 트리의 중간 노드를 기준으로 왼쪽과 오른쪽 서브트리를 재귀적으로 검사하여 유효한 트리 구조인지 확인한다. 

- 더미 노드가 실제 노드를 자식으로 가질 수 없기 때문에 이를 검증하는 과정이 필요하다. 

- 이 과정에서 유효한 트리로 변환할 수 있는지 여부를 체크하여 가능하면 1, 불가능하면 0을 반환 !

 

## 포화 이진 트리란? 

: 모든 레벨에 노드가 꽉 차 있는 트리 구조 

예를 들어, 높이가 3인 포화 이진 트리는 총 7개의 노드를 가지고 있다. 

 

### 노드 개수와 이진수 문자열 길이 

- 높이가 3인 이진 트리라면 7개의 노드를 가져야 한다. 

 

- 이진 트리의 노드 개수는 이 식으로 표현된다. 

 

### 포화 이진 트리로 변환 

- 주어진 이진수 문자열의 길이가 2^n-1이 되도록, 가장 가까운 2^n-1 값을 찾는다. 

- 예를 들어, 이진수 문자열의 길이가 5라면, 이를 포함할 수 있는 가장 가까운 포화 이진 트리의 노드 개수는 2^3-1 = 7이 된다. 

 

### 더미 노드 추가 

- 이진수 문자열의 길이가 2^n - 1 이 되도록 앞에 더미 노드 0을 추가한다. 

정답 풀이 코드 

function solution(numbers) {
    const answer = []; // 결과를 저장할 배열 초기화
    numbers.forEach((num) => {
        let bi_num = (num).toString(2); // 숫자를 이진수 문자열로 변환
        let n = bi_num.length; // 이진수 문자열의 길이
        let m = n.toString(2).length; // 이진수 길이를 이진수로 나타낸 문자열의 길이
        
        // 필요한 더미 노드 수를 계산하여 포화 이진 트리로 만듦
        let bi_tree = '0'.repeat(2 ** m - 1 - n); 
        bi_tree = bi_tree + '' + bi_num; // 포화 이진 트리 형태의 문자열 생성
        
        // 포화 이진 트리로 표현 가능 여부 확인
        if (checkBTree(bi_tree, 0, bi_tree.length - 1)) {
            answer.push(1); // 가능하면 1 추가
        } else {
            answer.push(0); // 불가능하면 0 추가
        }
    });
    return answer; // 결과 배열 반환
}

function checkBTree(b_str, start, end) {
    const mid = Math.floor((start + end) / 2); // 중간 노드 계산
    const left_c = Math.floor((start + mid - 1) / 2); // 왼쪽 자식 노드 계산
    const right_c = Math.floor((mid + 1 + end) / 2); // 오른쪽 자식 노드 계산
    
    if (start === end) {
        return true; // 리프 노드에 도달했을 때
    }
    
    // 현재 노드가 더미 노드('0')인데 자식 중 하나라도 실제 노드('1')인 경우
    if (b_str[mid] === '0' && ((b_str[left_c] === '1') || (b_str[right_c] === '1'))) {
        return false; // 불가능한 트리 형태로 간주
    }
    
    // 왼쪽 서브트리 확인
    if (!checkBTree(b_str, start, mid - 1)) return false;
    // 오른쪽 서브트리 확인
    if (!checkBTree(b_str, mid + 1, end)) return false;
    
    return true; // 모든 조건을 만족하면 가능
}

only 풀이 코드 

function solution(numbers) {
    const answer = []; 
    numbers.forEach((num) => {
       let bi_num = (num).toString(2)
       let n = bi_num.length; 
       let m = n.toString(2).length; 
       let bi_tree = '0'.repeat(2**m-1 -n); 
        bi_tree = bi_tree + '' + bi_num; 
        if (checkBTree(bi_tree, 0, bi_tree.length-1)) {
            answer.push(1);
        }
        else {
            answer.push(0);
        }
    })
    return answer; 
}

function checkBTree(b_str, start, end){
    const mid = Math.floor((start+end)/2); 
    const left_c = Math.floor((start+mid-1)/2); 
    const right_c = Math.floor((mid+1 + end)/2); 
    
    if(start === end){
        return true; 
    }
    
    if(b_str[mid] === '0' && ((b_str[left_c] === '1') ||  (b_str[right_c] === '1'))){
        return false; 
    }
    if(!checkBTree(b_str, start, mid-1)) return false; 
    if(!checkBTree(b_str, mid+1, end)) return false; 
    return true; 
        
}