프로그래머스 - 표현 가능한 이진트리

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

프로그래머스

 

1. 특징

1) dfs

2) 구현

 

2. 구현방법

1) 숫자를 이진수로 바꾼다

2) 포화이진트리의 개수에 맞춰 이진수의 앞에 0을 추가한다

3) 왼쪽 서브그래프, 중앙, 오른쪽 서브그래프를 dfs로 순회한다.

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

string hexToDec(long long cur)
{
    string ret;
    
    while(cur != 1)
    {
        if(cur%2 == 0) ret.insert(0, "0");
        else ret.insert(0, "1");
        cur/=2;
    }
    ret.insert(0, to_string(cur));
    return ret;
}

//포화이진트리노드개수: 2^n
string FullDec(string str) //101010 
{
    string ret = str;
    int idx = 2; // n == 1
    while(true)
    {
        if(str.size() <= idx-1) break; // 8
        else idx*=2;
    }
    
    for(int i = 0; i < idx-1-str.size(); i++) ret.insert(0, "0");
    
    return ret;
}

bool isAllZero(string str)
{
    for(char c: str)
    {
        if(c!='0') return false;
    }
    return true;
}
bool dfs(string str)
{
    if(str.size() == 1 || isAllZero(str)) 
    {
        return true;
    }
    
    if(str[str.size()/2] == '0') return false;
    
    
    string leftstr = str.substr(0, str.size()/2);
    string rightstr = str.substr(str.size()/2+1);

    if(dfs(leftstr) && dfs(rightstr)) return true;
    else return false;

}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    
    for(int i = 0; i < numbers.size(); i++)
    {
        long long cur = numbers[i];
        string str = hexToDec(cur);
        string fullstr = FullDec(str);
        answer.push_back(dfs(fullstr));

    }
    
    return answer;
}

4. 참고 블로그

https://algosu.tistory.com/152

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