문제

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

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

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

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

다음은 이진트리를 수로 표현하는 예시입니다.

주어진 이진트리는 다음과 같습니다.

주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.

노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.

당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.

이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ numbers의 길이 ≤ 10,000
  • 1 ≤ numbers의 원소 ≤ $10^{15}$

문제 링크

풀이

표현 가능한 이진트리라면 자식 노드가 있다면 그 부모 노드도 반드시 있어야한다.
부모가 0 이라면 그 자식도 0이어야만 하고, 자식 둘 중 하나라도 1이라면 표현 불가능한 이진트리다.

이진트리를 루트노드에서부터 리프노드까지 재귀적으로 탐색하는 dfs 함수를 작성하여 해결했다.

• 루트노드에서 처음 호출하고, 자식노드 위치에서 다시 dfs를 호출하는 재귀 함수이다.
• 호출된 위치가 리프노드라면 노드의 값에 상관없이 true를 리턴한다.
• 자식노드에서 호출된 dfs의 반환 값이 false라면 해당 dfs에서도 false를 반환한다.
• 현재 노드의 값이 0이라면 자식 노드의 값을 구하고 그 값이 둘 중 하나라도 1이라면 false 반환, 둘 다 0이라면 true를 반환한다.

자식노드 접근

부모노드에서 자식노드의 위치에서 dfs를 호출하거나 자식노드의 값을 얻기 위해서는 자식노드의 위치로 접근할 수 있어야 한다. 이를 위해 현재 노드의 위치와 노드의 depth(level) 값을 이용하여 자식 노드의 위치를 구하는 식을 알아야한다.

• 왼쪽 자식 노드 : $v-2^{n-1}$
• 오른쪽 자식 노드 : $v+2^{n-1}$

long long pow = 1 << level;
int left = v - pow/2;
int right = v + pow/2;

• v는 현재노드의 위치,
• level은 리프노드에서 루트노드까지의 depth를 거꾸로 센 값이다. ( 같은 level의 노드에서 가장 왼쪽 노드의 지수 값)

이진수 구하기

처음 이 문제를 풀때 numbers의 값들을 바로 비트 연산으로 접근하면 어짜피 이진수로 저장되어 있을 값을 이용하여 풀 수 있을 줄 알았다. 하지만 결국 이진수를 구해야만 해결이 가능했다.
그 이유는 numbers의 원소가 10의 15승이기 때문에 long long 자료형에 담겨야 하는데 이때 수의 크기가 32비트를 넘어가면 저장방식이 조금 달라진다.
단순하게 2진수로 저장되지 않는다는 사실을 모른채 계속 비트연산으로 접근하려니 numbers의 요소가 매우 큰 테스트 케이스에서는 통과되지 않았다.

그래서 결국 vector<bool>을 만들어서 2진수를 표현하고 해결했다.

for (auto n : numbers){
    long long pow = 1;
    int length = 0;
    long long root = 1;
    int level = 0;

    while (n > pow){
        pow *= 2;
        length += 1;
    }
    while (length >= root * 2){
        root *= 2;
        level += 1;
    }
    vector<bool> boolNum(root * 2, false);
    for (int i=0; i <= length; i++) {
        boolNum[i] = n % 2;
        n /= 2;
    }
}

• length: 이진수로 표현되었을 때의 길이
• root: 첫 dfs 호출을 위한 루트노드의 위치
• level: 자식노드에 접근하기 위한 값
• root * 2: 더미노드까지 포함하는 포화이진트리의 길이

코드

#include <string>
#include <vector>

using namespace std;


bool dfs(int64_t v, const vector<bool>& number, int32_t level){
    if (v % 2 == 1){ // 리프노드는 true 반환;

        return true;
    }
    
    long long pow = 1 << level;
    int left = v - pow/2;
    int right = v + pow/2;

    bool left_ret = dfs(left, number, level-1);
    bool right_ret = dfs(right, number, level-1);
    bool child = left_ret && right_ret;
    
    if (!child) { // 자식 둘 중 하나라도 false 라면

        return false;
    }
    


    if (!number[v-1]){

        bool left_res = number[left-1];
        bool right_res = number[right-1];

        // 둘 다 0 이여야함

        return !(left_res || right_res);

    }

    return true;
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for (auto n : numbers){
        long long pow = 1;
        int length = 0;
        long long root = 1;
        int level = 0;

        while (n > pow){
            pow *= 2;
            length += 1;
        }
        while (length >= root * 2){
            root *= 2;
            level += 1;
        }
        vector<bool> boolNum(root * 2, false);
        for (int i=0; i <= length; i++) {
            boolNum[i] = n % 2;
            n /= 2;
        }



        answer.push_back(dfs(root, boolNum, level));
    }

    return answer;
}

32비트 넘어가는 수는 왜 다르게 저장하는 것인지 모르겠다. 그것도 모르고 진짜 컴퓨터 부셔버릴뻔했다. 나중에 저장방법에 대해 찾아봐야겠다.