[카카오 블라인드 채용 2023] 표현 가능한 이진트리

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

프로그래머스

 

문제를 제대로 읽어봐야하는 문제이다. 이 문제는 결국에 '0'으로 표현되는 '더미 노드' 아래의 모든 자식 노드 역시 '더미 노드' 라면 표현 가능한 수인 것이다.

주어진 수를 이진수로 변환하고, root 부터 시작해서 자신의 양쪽 자식이 더미노드( 0 )인지 체크하고, 만약 '0'이라면 해당 자식 노드 하위의 모든 노드가 '0'  인지 체크하면 된다. 

 

보통의 이진트리는 아래와 같이 표현된다.

left_child_idx=parent_id*2

right_child_idx= parent_id*2+1 

하지만, 이 문제의 경우, 왼쪽에서 오른쪽으로 번호를 매기게 되어, 아래와 같이 새롭게 위치를 설정해야한다.

(h는 트리의 높이. root의 높이는 0)

left_child_idx=parent_id-2^(h-1)

right_child_idx= parent_id+2^(h-1)

 

 

정답 코드

#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
string bin(long long n){
    string ans="";
    while(n>0){
        char t= (char)(n%2) +'0';
        ans= t+ans;
        n/=2;
    }
    return ans;
}
vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for(auto n:numbers){
        string str=bin(n); 
        int len=1;
        while(len<=str.size()){//2,4,8,16..
            len*=2;
        }
        int dif=(len-1)-str.size();
        for(int i=0;i<dif;i++){
            str='0'+str; 
        }

        int root= len/2-1;
        queue<pair<int,int>> qu;    
        qu.push({root,len/2});
        bool chk=true;
        while(!qu.empty()){
            int parent=qu.front().first,nlen=qu.front().second;
            int lchild=parent-(nlen/2),rchild=parent+(nlen/2);
            qu.pop();
            if(str[parent]=='0'){
                for(int i=parent-(nlen-1);i<parent;i++){
                    if(str[i]=='1'){
                        chk=false;
                        break;
                    }
                }
                 for(int i=parent+1;i<=parent+(nlen-1);i++){
                    if(str[i]=='1'){
                        chk=false;
                        break;
                    }
                }
                if(!chk) break;
            }
            if(0<=lchild&&nlen!=0)
                qu.push({lchild,nlen/2});
            if(rchild<len&&nlen!=0)
                qu.push({rchild,nlen/2});
        }
        answer.push_back(chk);
    }
    return answer;
}