표현 가능한 이진트리

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

문제설명

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

이진트리를 수로 표현하는 방법은 다음과 같습니다.

1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.

이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

예를 들어 숫자 6은 다음과 같이 표현된다.

  1
 / \
1   0

이제 십진수값이 들어왔을 때, 위와 같은 규칙으로 트리를 형성할 수 있을지 판별하면 된다.

예를 들어 42와 7은 가능하지만, 5와 같은 경우는 불가능하다. 5를 이진수로 나타내면 101이다. 루트노드가 빈 상태의 트리인데, 이는 성립할 수 없다.

제한사항

1 ≤ numbers의 길이 ≤ 10,000

• 1 ≤ numbers의 원소 ≤ $10^{15}$

O(N * log(값)) 정도로 해결해야 시간제한에 걸리지 않을 것 같다.

해결과정

트리가 성립될 수 없는 식은 서브 트리의 루트 노드가 “0”인데, 왼쪽 혹은 오른쪽 서브트리의 전체가 0이 아닐 경우이다.

소스코드

#include <bits/stdc++.h>
using namespace std;
// 현재 binary가 정상적인 트리인가?
bool check(string binary){
    int s_size = binary.size();
    if(s_size == 1) return true;
    if((s_size + 1) % 2 != 0) return false;
    char mid = binary[s_size/2];
    string left = binary.substr(0, s_size/2);
    string right = binary.substr(s_size/2 + 1);
    //cout << left << ' ' << mid << ' ' << right << ' ';
    if(mid == '1'){
        return check(left) & check(right);
        
    }
    else{
        for(int i = 0; i<s_size/2; i++) 
            if(left[i] == '1') 
                return false;
        for(int i = 0; i<s_size/2;i++) 
            if(right[i] == '1') 
                return false;
        
        return true;
    }
    
}

string int2binary(long long in){
    string res;
    while(in){
        if(in & 1) res.push_back('1');
        else res.push_back('0');
        in = in >> 1;
    }
    long long string_size = res.size();
    long long padding_size = 0;
    for(long long i = 1;  ; i = i << 1){
        if(i > string_size){
            padding_size = i - string_size - 1;
            break;
        }
    }
    for(long long i = 0; i<padding_size; i++) res.push_back('0');
    return res;
}

vector<int> solution(vector<long long> numbers) {
    vector<int> ans;
    for(const auto& number : numbers){
        //cout << int2binary(number) << ' ';
        if(check(int2binary(number))){
            ans.push_back(1);
        }
        else ans.push_back(0);
    }
    return ans;
}