[프로그래머스,Java] Level3: 표현 가능한 이진트리

 

 

 

문제분석:

 

일단 문제부터 이해하는게 난관이다.

 

규칙:

1. 어떤 수가 있다면, 그걸 이진수로 바꾼다.

2. 표현된 이진수로  포화이진트리를 만든다.  {1 이면 있는노드 , 0이면 비어있는노드}

3. 만약 2번으로 포화이진트리가 안된다면, 0을반환, 된다면 1을반환한다.

 

 

단기간에 풀기에 조금 벅찬 느낌의 문제다.

 

일단 먼저 1번 과정을한다.

 

이진수로 바꾸는 과정이 필요하다.

흔한 이진수 로직이다. 하지만,  우리는 포화이진트리를 만들어야하기 때문에

 

포화이진트리의 갯수만큼 이진수를 늘려줘야한다. {비어있는부분을 0으로}

 

문제에서 요구하는건 포화이진트리를 만들어서 되는지를 묻기때문이다.

 

2번스텝으로 넘어간다.

표현된 이진수를  포화이진트리가 가능하게 만든다. 

 

포화 이진트리는  2^n -1 갯수이니  그만큼 더 늘려준다.

 

 

3번스텝이다. 여기가 제일 중요한 부분이다.

 

이젠 포화 이진트리가 가능한지를 판별해야한다.

 

포화 이진트리가 무조건 되는 경우를 구해보았다.

 

이진트리가 되려면 

1. 루트노드가 무조건 있어야함

2. 루트노드가 없다면, 왼쪽과 오른쪽  자식 노드가 무조건 0이여야함. { 왼, 오른노드가 있으면 에러}

 

이 2가지경우를 체크하면된다.

 

 

전체풀이:

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        int i=0;
        for(long num:numbers){        
            String binary =getBinary(num);
 
            if(isBinaryTree(binary)){
               answer[i]=1;
            }
            else{
               answer[i]=0;
            }
            i++;
        }
        return answer;
    }
    
    public String getBinary(long num){
        
        String str="";
        
        while(num!=0){
            
            if(num%2==1){
                str="1"+str;
            }else{
                str="0"+str;
            }
            num/=2;
        }
        
        //포화 이진트리 만들기
        int n=1;
        while(true){
            if(str.length()<=Math.pow(2,n)-1){
                break;
            }
            n++;
        }
        
        int add=(int)(Math.pow(2,n)-1)-str.length();
        for(int i=0;i<add;i++){
            str="0"+str;
        }
        
        return str;
    }
    
    public boolean isBinaryTree(String binary){
         
        if(binary.length()==1){
            return true;
        }
        int mid =binary.length()/2;
        
        int root = binary.charAt(mid);
          
        String left = binary.substring(0,mid);
        String right = binary.substring(mid+1);
        
        int leftRoot = left.charAt(left.length() / 2);
        int rightRoot = right.charAt(right.length() / 2);
        
        if(isBinaryTree(left)&&isBinaryTree(right)){
            if(root=='1'){
                return true;
            }
            if(leftRoot=='0'&&rightRoot=='0'){
                return true;
            }
        }
        
        return false;
    }
}