코딩테스트 -- 표현 가능한 이진트리 - (프로그래머스 / C++)

프로그래머스

 

문제!

 

---

---

요약하면 숫자를 포화 이진트리로 만들수 있는가를 출력해주는 문제였습니다!

 

약간 어려워 보였지만... 몇번 생각 해보니 약간 규칙이 있을것 같았습니다!

 

일단  3가지의 예제로 규칙을 만들어 보겠습니다!

111을 2진수로 변경하면 1101111

95를 2진수로 변경하면 1011111

42를 2진수로 변경하면 101010

 

위의 3가지 수들 중 먼저 포화 이진트리를 완성해야합니다. 

42의 경우 현재 1자리가 비어있는 상태입니다.

포화이진트리가 되려면 2의 제곱승-1 자릿수가 되어야 됩니다!

 

그러므로 앞부분에 수를 추가해줍시다!

42 >>> 0101010

 

그리고 이진트리가 되는경우를 생각해보면

3개씩 묶어 생각했을때 루트? (제일 위 노드) 가 존재하는경우  >> 무조건 만족

루트가 0인경우 >> 아래 노드들도 0이여야 만족

 

이렇게 2가지의 경우가 생깁니다. 

 

이 부분만 만족 시키면 되겠네요! 

 

처음에는 자릿수 계산을 하려 했지만 그건 숫자가 커질수록 복잡해져서 포기...

3개씩 묶어 계산하는 방식으로 풀어 보겠습니다.

 

먼저 111 >> 1101111

트리로 그려보면

           1

    1           1

1     0     1     1

 

이런식인데... 이렇게 보면 당연히 3개 만들어 지는 부분끼리 묶어낼수 있습니다.

110/ 1 / 111  >> 이런식으로 묶여집니다.

 

각각 연산해준다고 하면

110 >> 가능 ! 그리고 루트를 내보내 줍니다  >> 1

111  >> 가능 ! 그리고 루트를 내보내 줍니다 >> 1

 

1 / 1 / 1 >> 가능! answer.push(1)   끝!

 

이런식으로 연산 가능합니다. 

 

 

이제 95 >> 1011111 를 해보면

101 / 1 / 111

101 >>불가.... >> 0

111  >> 가능! >> 1

0 / 1 / 1 >> 가능! answer.push(1)   끝!

 

이런식으로 해결 가능해 보입니다! 바로 코드 시작!

 

 

가장 먼저 2진수 변경과 포화 트리를 만들기 위한 함수입니다.

string toBin(long long n){
    string temp;
    
    while(n>1){
        temp+=to_string(n%2);
        n/=2;
    }
    temp+=to_string(n);
    
    long long all =1; // 더미노드~ 
    long long count=0;
    
    while(1){
        if(all*2>temp.size()){
            all*=2;
            break;
        }
        all*=2;
    }
    count=all-temp.size()-1;
    while(count--){
        if(count<0){
            break;
        }
        
        temp+='0';
    }
    
    reverse(temp.begin(), temp.end());
    cout<<temp<<endl;
    return temp;
}

 

일반적인 2진수에서 포화 부분인 아래 부분만 조금 생각 해보시면 될것 같습니다!

count=all-temp.size()-1;
    while(count--){
        if(count<0){
            break;
        }
        
        temp+='0';
    }

이렇게 추가를 해주고 reverse함수로 돌려주면 포화 이진트리를 위한 이진수 완성!

 

 

다음은 메인 함수!

for(long long i:numbers){ // 숫자 하나씩 받기
        if(i==1){
            answer.push_back(1);
            continue;
        }
        string temp=toBin(i); // 바꾼것
        bool while_check=1;
        
        
        
        while(while_check){
            string temp_sort; //>> 3개씩 해서 맞는지 확인할것
            
            if(temp.size()==3){//마지막 처리
                answer.push_back(check(temp[1],temp[0],temp[2]));
                break;
            }
            
            for(int i=0;i<temp.size();i+=4){
                if(i!=0){  // 4칸 넘어갈때 중간노드 담아주기!
                    temp_sort+=temp[i-1];
                }
                
                if(check(temp[i+1],temp[i],temp[i+2])){
                    temp_sort+=temp[i+1];
                }
                else{ 
                    answer.push_back(0);
                    while_check=0;
                    break;
                }
            }
            temp=temp_sort;
        }
    }

여기서는 for 문을 i+=4를 하여 3개씩 끊어주며 넘어간 수들중 중간노드들을 추가해주는

부분만 주의 하시면 될것 같습니다.

 

그리고 중간중간나오는 check 함수는 3개씩 묶였을때 트리가 되는가를 해결해주는 함수로

bool check(char root, char nod1 ,char nod2){
    
    if(root=='0'){
        if(nod1=='0' && nod2 =='0'){
            return true;
        }
        return false;
    }
    
    return true;
    
}

끝...? 이 함수는 간단하게 구현했습니다.

 

 

여기까지가 끝!

 

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


using namespace std;

string toBin(long long n){
    string temp;
    
    while(n>1){
        temp+=to_string(n%2);
        n/=2;
    }
    temp+=to_string(n);
    
    long long all =1; // 더미노드~ 
    long long count=0;
    
    while(1){
        if(all*2>temp.size()){
            all*=2;
            break;
        }
        all*=2;
    }
    count=all-temp.size()-1;
    while(count--){
        if(count<0){
            break;
        }
        
        temp+='0';
    }
    
    reverse(temp.begin(), temp.end());
    cout<<temp<<endl;
    return temp;
}

bool check(char root, char nod1 ,char nod2){
    
    if(root=='0'){
        if(nod1=='0' && nod2 =='0'){
            return true;
        }
        return false;
    }
    
    return true;
    
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    
    for(long long i:numbers){ // 숫자 하나씩 받기
        if(i==1){
            answer.push_back(1);
            continue;
        }
        string temp=toBin(i); // 바꾼것
        bool while_check=1;
        
        
        
        while(while_check){
            string temp_sort; //>> 3개씩 해서 맞는지 확인할것
            
            if(temp.size()==3){//마지막 처리
                answer.push_back(check(temp[1],temp[0],temp[2]));
                break;
            }
            
            for(int i=0;i<temp.size();i+=4){
                if(i!=0){
                    temp_sort+=temp[i-1];
                }
                
                if(check(temp[i+1],temp[i],temp[i+2])){
                    temp_sort+=temp[i+1];
                }
                else{ 
                    answer.push_back(0);
                    while_check=0;
                    break;
                }
            }
            temp=temp_sort;
        }
    }
    
    return answer;
}

조금 길어졌지만 굳굳!

 

 

 

 

틀린점이 있다면 댓 달아주세요!