[Programmers] 표현 가능한 이진트리 [C++]

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

프로그래머스

 

문제 분석

숫자 numbers 가 주어질 때, 이 숫자를 이진수로 변환한 후, 이 이진수를 특정한 규칙에 따라 포화 이진트리로 변환해야 한다.

이진트리로 표현이 가능하다면 1, 없다면 0을 반환해야 한다

그렇다면 문제를 푸는 순서는 다음과 같다

1. 이진수로 변환
2. 포화 이진트리로 변환
3. 표현 가능한지 확인

이진트리로 표현할 수 있는 숫자에 규칙이 있을까?

 

입출력 예시인 7, 42, 5 를 한번 살펴보자

7 → 111 (변환 가능)

42 → 101010 (변환 가능)

5 → 101 (변환 불가능)

위 예시를 포화 이진트리로 바꾸면 두가지 규칙을 찾을 수 있다

1. 이진수의 중앙에 위치한 노드는 항상 루트 노드이다 + 0 이 될 수 없다
2. 포화 이진트리에서 부모 노드가 0 인경우 자식 노드가 0일 수 없다

위 규칙을 가지고 포화 이진트리가 주어졌다고 가정할 때, 우리는 재귀적으로 해당 이진트리가 표현 가능한지 불가능한지를 알 수 있다. (왼쪽, 중앙, 오른쪽 으로 나누어 검사 및 탐색)

#include <string>
#include <vector>

using namespace std;

string toDec(long long num){
    string ret = "";
    
    while(num){
        ret = to_string(num % 2) + ret;
        num /= 2;
    }
    return ret;
}

string fullDec(string s){
    string ret = s;
    int idx=  2;
    
    while(true){
        if(s.length() < idx) break;
        idx *= 2;
        
    }
    
    for(int i = 0; i< idx - 1 - s.length(); i++){
        ret = "0" + ret;
    }
    return ret;
}

bool possible(string s){
    if(s == "1") return true;
    bool allZero = true;
    for(int i = 0; i<s.length(); i++){
        if(s[i] == '1') allZero = false;
    }
    if(allZero) return true;
    
    
    int mid = s.length()/2;
    string left = s.substr(0, mid);
    string right = s.substr(mid + 1);
    if(s[mid] == '1' && possible(left) && possible(right)) return true;
    return false;
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for(const auto& num : numbers){
        string dec = toDec(num);
        string fDec = fullDec(dec);
        answer.push_back(possible(fDec));
    }
    return answer;
}