문제 링크

프로그래머스 문제

풀이

첫 시도는 사실 완전탐색으로 구현으로 풀려고 했다.
당연히 아니었다... 어쩐지 너무 쉽다 했다.

// 무식하게 풀려고 했으나 실패
function solution(numbers) {
    var answer = [];
    let num = 10000
    
    
    for(let i=0; i< numbers.length; i++){
        const curNumber = toMakeTwo(numbers[i])
        
        if(curNumber.length === 1){
            answer.push(1)
        }else if(curNumber.length === 3){
            if(check3(curNumber)){ //3자리 일때 가능한지
                answer.push(1)
            }else answer.push(0)
        }else if(curNumber.length === 7){
            //if() 7자리 일때 가능한지
            if(check7(curNumber)){
                answer.push(1)
            }else answer.push(0)
        }else if(curNumber.length === 15){
            if(check15(curNumber)){
                answer.push(1)
            }else answer.push(0)
            //if() 15자리 일때 가능한지
        }else{
            return 0 // 실패한 경우입니다. 그렇지만 예외는 없을겁니다.
        }
    }
    return answer;
}

function check15(n){
    
    if(n[7] === "0") return false;
    
    if(n[0] === "1"){
        if(n[1] === "0" || n[3] === "0" || n[7] ==="0"){
            return false
        }
    }
    
    if(n[2] === "1"){
        if(n[1] === "0" || n[3] === "0" || n[7] ==="0"){
            return false
        }
    }
    // 2번째
    if(n[4] === "1"){
        if(n[5] === "0" || n[3] === "0" || n[7] ==="0"){
            return false
        }
    }
    
    if(n[6] === "1"){
        if(n[5] === "0" || n[3] === "0" || n[7] ==="0"){
            return false
        }
    }
    // 4번째
    if(n[8] === "1"){
        if(n[9] === "0" || n[11] === "0" || n[7] ==="0"){
            return false
        }
    }
    
    if(n[10] === "1"){
        if(n[9] === "0" || n[11] === "0" || n[7] ==="0"){
            return false
        }
    }
    
    if(n[12] === "1"){
        if(n[13] === "0" || n[11] === "0" || n[7] ==="0"){
            return false
        }
    }
    
    if(n[14] === "1"){
        if(n[13] === "0" || n[11] === "0" || n[7] ==="0"){
            return false
        }
    }
    
    if(n[1] === "1"){
        if(n[3] === "0" || n[7] === "0"){
            return false
        }
    }
    
    if(n[5] === "1"){
        if(n[3] === "0" || n[7] === "0"){
            return false
        }
    }
    
    if(n[9] === "1"){
        if(n[11] === "0" || n[7] === "0"){
            return false
        }
    }
    
    if(n[13] === "1"){
        if(n[11] === "0" || n[7] === "0"){
            return false
        }
    }
    
    return true;
    
}


function check7 (n){
    if(n[0] === "1"){
        if(n[1] === "0" || n[3] === "0"){
            return false
        }
    }
    
    if(n[2] === "1"){
        if(n[1] === "0" || n[3] === "0"){
            return false
        }
    }
    
    if(n[4] === "1"){
        if(n[5] === "0" || n[3] === "0"){
            return false
        }
    }
    
    if(n[6] === "1"){
        if(n[5] === "0" || n[3] === "0"){
            return false
        }
    }
    
    if(n[3] === "0"){
        return false
    }
    
    return true
    
    
}

function check3 (curNumber){
    if((curNumber[0]==="1" || curNumber[2] ==="1")){
        if(curNumber[1]==="1")
        return true
        else return false
    }else if(curNumber[0]!=="1" && curNumber[2]!=="1" && curNumber[1]==="1"){
        return true
    }else{
        return false
    }
}

function toMakeTwo (number) {
    number = number.toString(2)
    
    let LEN = 0;
    if(number === 1){
        return 1
    }
    if(number.length <=3){
        LEN = 3
    }else if(number.length <= 7){
        LEN = 7;
    }else if(number.length <= 15){
        LEN = 15;
    }else{
        LEN= 32
    }
    
    while(number.length !== LEN){
        number = "0"+ number
    }
    
    return number
}

// 3 7 15 31,

굉장히 부끄러운 코드다.
이번엔 정말 이진트리를 만들어 본다.
-> 근데 이진트리를 만들기 보다는,
재귀함수로 구현할 수 있다는 힌트를 받아서 풀게 되었습니다.

코드

function solution(numbers) {
    var answer = [];
    let num = 10000
 
    
    
    for(let i=0; i< numbers.length; i++){
        if(numbers[i] === 1){
            answer.push(1)
            continue;
        }
        const curNumber = toMakeTwo(numbers[i])

        if( checkTree (curNumber, 0, curNumber.length-1) ){
               answer.push(1)
        }else answer.push(0)
        
    }
    return answer;
}


function check3 (curNumber){
    if((curNumber[0]==="1" || curNumber[2] ==="1")){
        if(curNumber[1]==="1")
        return true
        else return false
    }else if(curNumber[0]!=="1" && curNumber[2]!=="1" && curNumber[1]==="1"){
        return true
    }else{
        return false
    }
}

function toMakeTwo (number) {
    number = number.toString(2)
    
    let LEN = 0;
    if(number.length === 1){
        return 1
    }
    if(number.length <=3){
        LEN = 3
    }else if(number.length <= 7){
        LEN = 7;
    }else if(number.length <= 15){
        LEN = 15;
    }else if(number.length <= 31){
        LEN= 31
    }else {
        LEN = 63
    }
    
    while(number.length !== LEN){
        number = "0"+ number
    }
    
    return number
}

function checkTree (array, start, end) {
    
    if (start == end) {
        return true;
    }
    
    //부모 노드 idx
    const mid = Math.floor((start+end) / 2);
    //자식 노드 idx
    const left = Math.floor((start+mid-1)/2);
    const right = Math.floor((mid+1 + end)/2);
    
    if(((array[left] === '1') || (array[right] === '1'))){
        if(array[mid] === '0'){
            return false
        }
    }
    
  
    if (!checkTree(array, start,  mid-1)) return false;
    if (!checkTree(array, mid+1,    end)) return false;
    
    return true;
}
// 3 7 15 31,