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

---

 

1. 주어진 십진수를 이진수로 변환한다.
2. 변환한 이진수는 트리를 중위순회한 결과와 같다.
3. 중위순회 결과를 가지고 포화이진트리를 만들었을 때, 부모는 더미노드인데 자식은 실제노드인 경우 표현 불가능한 구조이다.

 

1. 주어진 십진수를 이진수로 변환한다.

 먼저 십진수를 이진수로 변환한다.

 

2. 변환한 이진수는 트리를 중위순회한 결과와 같다.

 노드를 왼쪽부터 순서대로 살펴보는 것은 중위순회하는 것과 같다. 따라서 변환한 이진수는 트리를 중위순회한 결과와 같고, 이진수의 길이는 트리의 노드 개수와 같다. 포화이진트리는 노드의 개수가 2^n-1개이므로 포화이진트리가 되도록 부족한 길이는 0으로 채워준다. (더미 노드를 추가하는 것은 문제가 되지 않음)

 

3. 중위순회 결과를 가지고 포화이진트리를 만들었을 때, 부모는 더미노드인데 자식은 실제노드인 경우 표현 불가능한 구조이다.

 이제 중위순회 결과를 가지고 포화이진트리를 만들자. 노드 개수가 n인 포화이진트리라면 루트는 정중앙인 (n+1)/2번째에 위치한다. 이제 루트를 기준으로 왼쪽 이진수는 왼쪽 서브트리를 이루고, 오른쪽 이진수는 오른쪽 서브트리를 이룬다. 이제 재귀적으로 두 서브트리에 대해서도 루트와 서브트리를 구할 수 있다.

 이때 모순되는 경우는 '부모는 더미노드인데, 자식은 실제노드인 경우'이다. 이진트리를 수로 표현하는 과정에서 실제노드를 추가할 수는 없다. 따라서 원래 존재하던 실제노드들의 부모는 반드시 원래 존재하던 실제노드일 수 밖에 없기 때문이다.

---

#include <string>
#include <vector>

using namespace std;

vector<bool> binary;

// check(lo, hi): 이진트리를 중위순회한 결과가 binary일 때, 서브트리 [lo,hi]가 가능한 구조인지 검사하는 함수
bool check(int lo, int hi) {
    if (lo == hi) return true;
    
    int mid = (lo + hi) / 2;    // 루트
    int lc = (lo + mid-1) / 2;  // 왼쪽 자식
    int rc = (mid+1 + hi) / 2;  // 오른쪽 자식
    
    // 부모가 0인데 자식이 1인 것은 불가능
    if (!binary[mid] && (binary[lc] || binary[rc])) {
        return false;
    }

    return check(lo, mid-1) && check(mid+1, hi);
}

// calcIdealSize(curr_len): 현재 노드 개수가 curr_len개일 때, 포화이진트리로 만들 경우 전체 노드의 개수
int calcIdealSize(int curr_size) {
    for (int i=1; i<=6; i++) {
        // 포화이진트리의 노드 개수는 2^n - 1개
        int len = (1 << i) - 1;
        if (curr_size <= len) return len;
    }
    
    return -1;
}

// toBinary(n): 십진수 n을 이진수로 변환하는 함수
void toBinary(long long n) {
    while (n > 0) {
        binary.push_back(n % 2);
        n /= 2;
    }
    
    // 빈 곳은 모두 더미노드(0)로 채워서 포화이진트리로 만들기
    int ideal_size = calcIdealSize(binary.size());
    while (binary.size() < ideal_size) {
        binary.push_back(0);
    }
}

void initTestcase() {
    binary.clear();
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    
    for (auto number: numbers) {
        initTestcase();
        
        toBinary(number);
        answer.push_back(check(0, binary.size()-1));
    }
    
    return answer;
}