[JAVA] Programmers 표현 가능한 이진트리

풀이 방법

1. Queue를 이용하여 각각의 상위 parent의 node 값을 저장해준다.
2. convert 함수를 통해 num을 이진수로 변환한다.
   1. 이때 예시의 63을 생각해보면 원래의 이진수는 1부터 시작해야 한다.
   2. 그러므로 완전 이진트리를 생각했을 때 이진수의 길이에 값을 맞추기위해 앞에 0을 추가해야 함을 생각하자.
   3. 가능한 이진수의 길이는 nums 배열에 저장해두었다.
   4. 가능한 이진수의 길이가 되게 하기 위해 그만큼 앞에 0을 추가해주자
3. check 함수를 통해 이진트리가 되는지 확인한다.
   1. 짝수의 경우 미리 저장해둔 roots배열을 확인한다.
   2. 홀수의 경우 4로 나눈 나머지가 1인 친구들과 2인 친구들에 따라 parent가 다르다.
   3. 가능한 이진트리가 되려면 자식이 존재하는 경우 부모가 존재해야 한다.

import java.util.*;

class Solution {
    static int[] nums = {1, 3, 7, 15, 31, 63};
    static int[] roots;
    public int[] solution(long[] numbers) {
        int N = numbers.length;
        int[] answer = new int[N];
        roots = new int[64];
        // Queue 사용하기
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{32, 16});
        while(!q.isEmpty()){
            int[] now = q.poll();
            if(now[1] == 1) break;
            roots[now[0]-now[1]] = now[0];
            roots[now[0]+now[1]] = now[0];
            q.offer(new int[]{now[0]-now[1], now[1]/2});
            q.offer(new int[]{now[0]+now[1], now[1]/2});
        }
        for(int i=0; i<N; i++){
            String c = convert(numbers[i]);
            answer[i] = check(c);
        }
        return answer;
    }
    static int check(String s){
        int root = s.length()/2+1;
        for(int i=1; i<=s.length(); i++){
            if(i == root) continue;
            if(i % 4 == 1 && s.charAt(i-1) == '1'){
                if(s.charAt(i) == '0') return 0;
            }
            else if(i % 4 == 3 && s.charAt(i-1) == '1'){
                if(s.charAt(i-2) == '0') return 0;
                
            }
            else if(i % 2 == 0 && s.charAt(i-1) == '1'){
                if(s.charAt(roots[i]-1) == '0') return 0;
            }
        }
        return 1;
    }
    static String convert(long num){
        String r = "";
        while(true){
            r = (num % 2) +r;
            if(num == 0 || num == 1) break;
            num /= 2;
        }
        for(int i=0; i<6; i++){
            if(r.length() == nums[i]) return r;
            if(r.length() < nums[i]){
                int N = nums[i]-r.length();
                for(int j=0; j<N; j++)
                    r = "0"+r;
                return r;
            }
        }
        return r;
    }
}