표현 가능한 이진트리 [Lv.3]

프로그래머스

 

수를 입력받고 이 수를 이진트리로 만들 수 있는지 확인하는 문제입니다.

조건은 노드의 값이 1일때만 자식 노드를 가질 수 있습니다.

 

 

풀이 방법

1. 입력받은 수를 이진수로 변환

2. 이진수를 이진트리로 변환하였을때 포화이진수가 되게끔 '0'을 추가

3. 중간값을 기준으로 좌 우로 string을 나누어 재귀

4. 3개의 값이 있을때 중간값이 0이면 false 아니면 true 반환

 

정답 코드

string itob(long long i)
{
    string r;
    while (i > 0)
    {
        r = to_string(i % 2) + r;
        i /= 2;
    }
  
    int n = 2;
    while (n < r.size() + 1)
        n = n * 2;

    while (n  > r.size() + 1)
        r = '0' + r;
    
    return r;
}

 입력받은 수를 이진수로 변환해주며 포화이진트리가 되게끔 0을 추가해주었습니다.

 

bool check(string str)
{
    if (str.size() == 1 || isAllZero(str)){
        return true;
    }
        
    int mid = str.size() / 2;
    string left = str.substr(0, mid);
    string right = str.substr(mid + 1);

    return str[mid] == '1' && check(left) && check(right);
}

str 사이즈가 1이거나 모두 0이면 true를 반환합니다.

반환 후 mid 값이 1이면 true 아니면 0을 반환합니다.

 

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    
    for (int i = 0; i < numbers.size(); i++)
    {
    //    cout << itob(numbers[i]) << "\n";
        if (check(itob(numbers[i])))
            answer.push_back(1);
        else
            answer.push_back(0);
    }
    
    return answer;
}