[프로그래머스] Level 3. 표현 가능한 이진트리

 

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

프로그래머스

 

해결 방법

1. 주어진 수를 이진수로 변환하고, 배열 num에 넣는다.
2. 이진수 배열 num를 이용해 이진트리를 만든다.
3. 이진트리가 적합한지 판단한다. 만약 더미노드가 1을 자식으로 보유하고있다면, 적합하지 않다는 의미이다

주의할 점

• 이진수 배열 num의 개수를 꽉찬 이진트리 개수와 맞게 해야한다. 이진수가 모두 들어갈 수 있는 이진트리의 depth를 찾아 총 필요한 노드의 개수를 찾고, 앞을 0으로 채운다.
• 이진수 배열 num은 거꾸로 저장되어있다. num이  1011000 으로 저장되어있을 경우,  실제 이진수는 0001011 이고, 이진트리를 맞추기위해 0을 2개 더 붙인 구조이다.
• setTree() 함수는 이진배열 num을 이용해 이진트리를 구성하는 함수이다. 배열을 절반으로 나누어서 가운데 있는 수가 부모노드, 절반을 갈라서 왼쪽에 있는 수는 오른쪽 자식노드, 반을 갈라서 오른쪽에 있는 수들은 왼쪽 자식 노드에 들어올 숫자들이다. (num이 거꾸로있기 때문에)
• 해당 노드가 0이고, 자식노드가 1인 경우가 있으면 유효하지 않은 트리이다. 더미노드 0 이 단지 자식을 보유하고 있다고 해서 false 는 아니다. 두 자식 모두 더미노드 일 경우는 true인 트리이다. (이것 때문에 처음에 실패나왔다)

#include <string>
#include <vector>
#include <cmath>

using namespace std;

void setTree(const vector<int>& num, vector<int>& tree, int s, int e, int idx){
    if(idx < 0 || idx >=tree.size() || s>e) return;
    
    int numIdx = (s+e)/2;
    tree[idx] = num[numIdx]; //정 가운데에 있는 애가 부모노드임.
    setTree(num,tree,numIdx+1,e,idx*2+1); //왼쪽트리 세팅.
    setTree(num,tree,s,numIdx-1,idx*2+2); //오른쪽 트리 세팅
    
}

bool existTree(long long number){
	//이진수가 거꾸로 들어있는 배열 num을 만듬
    vector<int> num;
    while(number != 0){
        num.push_back(number%2);
        number /=2;
    }
    
    //깊이 몇개짜리인지 찾음.
    int depth = 1;
    long long size = 1;
    while(size < num.size()){
        depth++;
        size += pow(2,depth-1);
    }
    
    while(num.size() != size) num.push_back(0); //앞에 사이즈 맞출 0을 넣어줌.꽉 찬 이진트리 개수를 맞추기 위함.

	vector<int> tree(size);
    setTree(num, tree,0,tree.size(),0);
    
    //이진트리 검사
    for(int i=0; i<tree.size(); i++){
        if(tree[i] == 0){
            //자식이 한개라도있으면. 리프 노드가 아닌데 0이라는 의미.
            if(i*2+1 >= tree.size()) continue; //리프노드는 0이어도 됨.
            if(tree[i*2+1] != 0||tree[i*2+2] !=0) return false;
        }
    }
    return true;
}



vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for(int i=0; i<numbers.size(); i++){
        bool exist = existTree(numbers[i]);
        answer.push_back(exist?1:0);
    }
    return answer;
}

 

 

 

마무리 하며

 

1) 이진트리를 만드는것

2)유효한 트리인지 검사하는 것 

두가지 포인트였다. 이진트리를 만드는 부분에서 약간의 어려움이 있었으나 잘 이겨냈다. 반씩 갈라서 재귀적으로 트리를 만드는것은 내가만들었지만 정말 아름답구나 ㅎㅎㅎ 이맛에 알고리즘한다~