[프로그래머스 Level 3] 표현 가능한 이진트리 (C++)

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

프로그래머스

 

 

접근 방식은 먼저 주어진 수를 이진수로 변환한 후 포화 이진 트리 형식으로 만들어준다. 포화 이진 트리 형식으로 만들 때 비트의 개수가 1, 3, 7, 15, 31, 63 중에서 하나이어야 한다. 따라서 이 값이 안 되면 맨 앞 비트에 0을 붙여준다.

이후 dfs를 돌면서 트리에서 자식 중 하나라도 1일 때 부모가 0이면 0의 값을 넣어주도록 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <memory.h>

using namespace std;

string toBinary(long long x){
    string binary = "";
    while(x != 0)
    {
        if (x % 2 == 1) // 나머지가 1
            binary+="1";
        else            // 나머지가 0
            binary+="0";
        
        x /= 2;
    }
    reverse(binary.begin(), binary.end());
    
    return binary;
}

string toRealBinary(string s){
    size_t c = s.size();
    if(c<=1){
        return s;
    }else if(c<=3){
        for(int i = 0 ; i<3-c; i++){
            s="0"+s;
        }
        return s;
    }else if(c<=7){
        for(int i = 0 ; i<7-c; i++){
            s="0"+s;
        }
        return s;
    }else if(c<=15){
        for(int i = 0 ; i<15-c; i++){
            s="0"+s;
        }
        return s;
    }else if(c<=31){
        for(int i = 0 ; i<31-c; i++){
            s="0"+s;
        }
        return s;
    }else{
        for(int i = 0 ; i<63-c; i++){
            s="0"+s;
        }
        return s;
    }
}

string remote;

int dfs(int s, int e){
//    cout<<s<<" "<<e<<endl;
    int c = (s+e)/2;
    if(e-s==2){
        if(remote[c-1]=='1'||remote[c+1]=='1'){
            if(remote[c]=='0'){
                return 0;
            }
        }
        return 1;
    }
    
    if(remote[(s+c-1)/2]=='1' || remote[(c+1+e)/2]=='1'){
        if(remote[c]=='0'){
            return 0;
        }
    }
    
    
    return dfs(s, c-1)&&dfs(c+1,e);
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for(long long number : numbers){
        if(number==1){
            answer.push_back(1);
            continue;
        }
        string binary = toBinary(number);
        binary = toRealBinary(binary);
        remote = binary;
        answer.push_back(dfs(0, (int)remote.size()-1));
    }
    return answer;
}