[Lv.3] 표현 가능한 이진트리

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        for (int j = 0; j < numbers.length; j++) {
            long number = numbers[j];
            String s = Long.toBinaryString(number);
            int length = s.length();

            for (int i = 1; i < 52; i++) {
                double pow = Math.pow(2, i)-1;
                if (length > pow)
                    continue;
                if (length == pow) {
                    //딱 i레벨의 수를 만들었다.
                    if (checkTree(s)) {
                        answer[j] = 1;
                        break;
                    }
                } else {
                    String target="";
                    for (int k = 0; k < pow - length; k++) {
                        target+="0";
                    }
                    target+=s;
                    if(target.charAt((int) (pow/2))=='0')
                        break;
                    if(checkTree(target)) {
                        answer[j] = 1;
                        break;
                    }
                }

            }
        }
        return answer;
    }
    public boolean checkTree(String number){
        Queue<String> targetList=new LinkedList<>();
        targetList.add(number);
        while (!targetList.isEmpty()){
            String poll = targetList.poll();
            int length = poll.length();
            if(length==1)
                continue;
            if(poll.charAt(length/2)=='0'){
                //이 밑에 모두 다 0이면 가능하다.즉 하나라도 1이 있으면 안된다.
                for (int i = 0; i < poll.length(); i++) {
                    if(poll.charAt(i)=='1')
                        return false;
                }
                //이미 다 0이면 추가로 분화할 이유가 없다.
            }else{
                //가운데가 1이면 집합을 두개로 나눌 수 있다.
                String substring1 = poll.substring(0, length / 2 );
                String substring2 = poll.substring(length/2+1, length);
                targetList.add(substring1);
                targetList.add(substring2);
            }
        }

        return true;
    }
}

---

DP로 이 문제를 풀려하면 시간초과가 날 수 밖에 없다.

원소가 10^15까지 가능하므로 약 2^51까지 표현해야 하는데 이걸 다 만들기엔 경우의수가 너무 많다.

 

따라서, 다른 방법이 필요하다.

 

내가 생각한 방법은, 전달받은 수를 2진수로 변환하고 이를 포화 2진트리에 매핑하는 것이다.

포화 2진트리는 2^n-1개의 노드를 가지고 (n개의 레벨에 대해서) 문제에서 최대 2^51의 수를 표현해야 하니 넉넉하게 레벨을 1개부터 51개까지 늘려가며 반복을 시작한다.

매 반복에선, 현재 문자열의 길이가 현재 반복의 노드 수보다 크다면 다음 레벨로 넘어가고 같다면 현재 수를 이용해서 포화이진트리를 만들 수 있는 지 확인한다. 그리고, 문자열 길이가 더 작아지게 되면 현재레벨의 포화 이진트리의 노드수에 맞게끔 앞에 0을 더 붙여준 후 포화이진트리 여부를 확인한다.

 

포화이진트리 여부는 간단하다.

level 3를 생각해보면 xxx0xxx 혹은 xxx1xxx의 형태이다.

여기서 가운데가 0이라면 해당 트리의 왼쪽, 오른쪽 자식은 모두 0이어야 한다. 그러므로, 1이 발견되면 즉시 false를 리턴한다.(부모가 없는데 자식이 존재할 수 없다.)

즉, 모두 0인지 확인해보고 모두 0이라면 해당 서브트리는 더이상 확인할 필요가 없으므로(이미 다0이니깐..) 넘어간다.

 

하지만, 가운데가 1이라면 왼쪽 오른쪽 자식트리가 모두 존재할 수 있다. 따라서, 가운데를 기준으로 반반씩 나누어 다시 검사 큐에 넣는다.

(XXX 1 XXX를 (XXX),(XXX)로 나누어 두 집합을 검사 큐에 넣고 동일한 검사를 다시 진행한다.)

이렇게 검사큐가 빌때까지 혹은 반복이 끝날 때까지(리프 서브트리는 그냥 리프노드이기에 크기가 1이고 이때는 검사를 진행하지 않는다) 

이렇게 검사가 끝날 때까지 false가 리턴되지 않았으면 (포화 이진트리를 만들 수 있었다면) 마지막으로 true를 리턴한다.