[프로그래머스] 표현 가능한 이진트리 (c++)

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

프로그래머스

 

풀이 방법

문제를 이해한다.

 

트리에서 중위순회를 통해 빈 노드는 0, 존재하는 노드는 1로 표현된다는 것을 알 수 있다. 또한, 문제의 예시에서 7과 42가 같은 트리로 표현되며, 42는 생략된 노드가 많아 이러한 표현이 가능하다는 점을 이해한다.

 

문제 풀이 방법

1. 10진수를 2진수로 변환한다.

2. 2진수를 완전 이진트리로 변경할 수 있도록 부족한 노드 수만큼 앞에 0을 추가한다.

 

2진수에 생략된 0을 추가하는 과정

 

완전 이진트리의 특성을 고려한다.

완전 이진트리의 노드 개수는 1, 3, 7, 15, 31...로, 2^n - 1의 형태를 가진다.

따라서:

• 10진수를 2진수로 변환한 뒤,

• 변환된 이진수의 길이보다 크면서 2^n - 1 중 가장 작은 값을 선택한다.

• 그 값과의 차이만큼 앞에 0을 추가하여 완전 이진트리 형태로 만든다.

 

완전 이진트리 가능 여부 확인

 

완전 이진트리를 만들 수 있는지 확인하기 위해 다음 조건을 검토한다:

• 부모가 0인 경우: 자식 노드들도 모두 0이어야 한다.

• 부모가 1인 경우: 왼쪽 서브트리와 오른쪽 서브트리가 각각 완전 이진트리를 구성할 수 있어야 한다.

 

탐색 방식

• 분할 정복을 사용하여 왼쪽 서브트리와 오른쪽 서브트리를 탐색한다.

• 종료 조건: 리프 노드의 경우, 값이 0이든 1이든 상관없이 조건을 만족하므로 true를 반환한다.

 

이 과정을 통해 입력된 값을 기반으로 완전 이진트리를 만들 수 있는지 판단한다.

코드

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

long long near_two_power(long long n) {
    //만약 n이 1이 들어오게 된다면 
    long long temp = 2;
    while(n > temp - 1) {
        temp = temp * 2;
    }
    return temp - 1;
}

string ten_to_binary(long long num) {
    long long temp = num;
    string binary;    
    while(temp > 0) {
        binary += (temp % 2) + '0';
        temp = temp / 2;
    }
    //0을 추가해 주어야 한다.
    long long extra = near_two_power(binary.size());
    long long now_size = binary.size();
    for (long long i = now_size;i < extra;i++) {
        binary += '0';
    }
    reverse(binary.begin(), binary.end());
    return binary;
}

bool divide_conquer(string num, int left, int right) {
    if (left == right) return true; // 리프 노드
    
    int mid = (left + right) / 2;        
    if (num[mid] == '0') { // 모두 0이어야 한다.
        for (int i = left;i <= right;i++) {
            if (num[i] == '1') return false;
        }
        return true;
    }    
    else {
        return divide_conquer(num, left, mid - 1) && divide_conquer(num, mid+1, right);
    }
}
int sol(long long num) {
    string binary = ten_to_binary(num);            
    if (divide_conquer(binary, 0, binary.size() - 1)) {        
        return 1;
    }
    else return 0;
    
}
vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for (int i = 0;i < numbers.size();i++) {
        answer.push_back(sol(numbers[i]));
    }    
    return answer;
}