문제 150367. 표현 가능한 이진 트리(카카오 코테)

문제 링크

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

프로그래머스

 

난이도 : Lv.3

 

문제 요약 설명

숫자 num이 주어졌을 때 해당 수를 완전 이진 트리로 표현할 수 있으면 1, 아니면 0을 반환한다. 숫자는 배열 형태(numbers)로 여러 개 주어진다. 완전 이진 트리를 만드는 방법은 다음과 같다. 

• 임의의 이진 트리를 만든다. 
• 이진 트리의 모든 부모 노드는 왼쪽 자식 노드의 서브 트리보다 순서가 낮으며, 오른쪽 자식 노드의 서브 트리보다 순서가 높다. (순서 오름차순: 왼쪽 자식 -> 부모 -> 오른쪽 자식)
• 부모 노드의 왼쪽 또는 오른쪽 자식 노드가 없는 경우, 해당 위치에 더미 노드를 추가한다. 더미 노드는 0, 일반 노드는 1을 의미한다. 이로써 이진 트리는 완전 이진 트리가 된다.
• 완전 이진 트리에서 순서가 높은 노드부터 차례대로 읽었을 때, 주어진 숫자의 이진수와 비트패턴이 같다면 해당 숫자는 이진 트리로 표현할 수 있다고 한다.

입력

표현 가능한 지 알고 싶은 숫자들이 들어있는 vector<long long> numbers가 주어진다.

 

입력 제한

1 ≤ numbers의 길이 ≤ 10,000
1 ≤ num ≤ 10^15

입력 예제

// input
[7, 42, 5]

// ans
[1, 1, 0]

 

 

풀이 방식

알아낸 사실

• 이진 트리로 표현할 수 있으려면 유일무이한 규칙, "부모 노드가 더미 노드(0)면 자식노드가 일반 노드(1)일 수 없다."를 만족해야한다. 그렇기 때문에 해당 조건에 만족하지 않는 지만 판단하면 된다.
• 완전 이진 트리는 노드의 개수는 2^N -1이다. 입력되는 숫자의 범위가 long long(63비트)이니 127개가 완전 이진 트리의 최대 노드 개수다. 즉, 각 숫자당 만들 수 있는 완전 이진 트리 후보는 10개도 안된다.
• 신경 써야 할 더미 노드의 자리는 가장 왼쪽 밖에 없다. 중간이나 오른쪽에 포함된 더미 노드는 고정으로 들어가기 때문. 하지만, 가장 왼쪽에 들어가는 더미 노드들의 경우 개수에 따라 완전 이진 트리의 최상단 루트가 바뀐다.

그래서?

주어진 숫자를 이진수로 변환하고, 해당 이진수로 만들 수 있는 완전 이진 트리들을 만든 다음, 표현할 수 있는 완전 이진 트리인지 확인하면 된다. 확인은 분할 정복 알고리즘(Divide and Conquer)를 이용해 해당 이진 트리의 모든 서브 트리가 "부모 노드가 더미 노드(0)면 자식노드가 일반 노드(1)일 수 없다."는 조건을 만족하는지 확인하면 된다. 사용한 분할 정복 알고리즘은 O(n)이기 때문에 재귀라는 것 빼곤 꽤 합리적이다.

 

정답 코드 

블로그에 포스팅한 코드는 전부 깃헙에 올라가 있습니다.

#include <bits/stdc++.h>

using namespace std;

// num의 이진수 표현을 반환.
string getBinary(long long num){
    string str_num = "";
    while(num > 0){
        str_num += (num % 2) + '0';
        num /= 2;
    } 
    
    reverse(str_num.begin(), str_num.end());
    
    return str_num;
}

// 현재 트리가 표현 가능한 이진 트리라면 true, 아니라면 false를 반환.
// str_num: 현재 문자열, idx: 서브 트리의 루트 위치, len: 현재 서브 트리의 한 쪽 길이
bool divAndConq(string str_num, int idx, int len){
    
    int left_idx = idx - len/2 - 1;
    int right_idx = idx + len/2 + 1;
          
    //printf("left_idx: %d, right_idx: %d idx: %d len: %d\n", left_idx, right_idx, idx, len);
    if(str_num[idx] == '0' && (str_num[left_idx] - '0' || str_num[right_idx] - '0')){      
        //printf("str_num: %s, idx: %d (%d %d %d)\n", str_num.c_str(), idx, str_num[idx]-'0', str_num[left_idx]-'0', str_num[right_idx]-'0');
        return false;
    }
    
    if(len <= 1) return true;
    
    return divAndConq(str_num, left_idx, (len-1)/2) && divAndConq(str_num, right_idx, (len-1)/2);
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    
    for(long long num : numbers){
        // 십진수를 이진수로 변경.
        string str_num = getBinary(num);
           
        int len = str_num.length();
        bool ans = false;
        string dummies = "";
        vector<int> v1 = {1, 3, 7, 15, 31, 63, 127};    // 완전 이진 트리의 노드 개수 목록
        for(int i = 0; i < v1.size(); i++){   
            
            dummies = "";
            
            // 가능한 이진 트리의 크기를 구한다. 
            if(len > v1[i]) continue;   
            else if(len < v1[i]) dummies.append(v1[i] - len, '0');
            
            // 문자열과 문자열이 길이를 더미 양에 따라 재설정.
            string cur_str_num = dummies + str_num;            
            int cur_len = cur_str_num.length();
            
            // 현재 문자열이 표현 가능한 이진트리라면 true 설정 및 for문 탈출.
            if(divAndConq(cur_str_num, (cur_len-1)/2, (cur_len-1)/2)){
                ans = true;
                break;
            }
            
        }
             
        answer.push_back(ans);
               
    }
    
    return answer;
}

 

더 좋은 풀이?

 

- 추후 업데이트..?