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

문제 설명

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

문제 풀이

• DFS로 풀이 하였다.
• 문제는 크게 2단계로 구성된다.

  1. 특정수를 포화이진트리 크기에 맞게 이진수로 변경 (포화이진트리 이진수이라 명명)
  2. DFS로 포화이진트리 이진법을 validation

• 1번의 의미는 다음과 같다.

  • 포화 이진트리의 원소수는 높이에 따라 2^(트리높이) - 1 가 된다.
  • 해당수를 포화이진트리 이진법으로 변환해야 특정 구간에서 mid = root를 만족하여 dfs 탐색 가능 하다
  • 포화이진트리 이진수 길이를 구하는 방식은 다음과 같다.
    1. 해당 수의 이진법 길이 = floor(log2(num)) + 1
    2. 포화이진트리 이진수 길이 = n을 1씩 늘려가며 2^n-1을 구하되 처음 이진법 길이보다 커지는 2^n - 1

• 위처럼 해당 수에 맞는 포화이진트리 이진수 길이를 구하면 이진법 수를 오른쪽부터 체우고 남은 왼쪽은 0으로 패딩해주면 포화이진트리 이진수가 완성된다.
• 이후 포화이진트리 이진법을 대상으로 dfs로 validation을 해주면 된다.

소스 코드 (JAVA)

class Solution {
    public boolean[] target; //2진법으로 변환한 배열 (좌측 0 패딩 포함
    public int result;

    //Root 부터 탐색
    public void solve(int s, int e, boolean isEnd) {
        int mid = (s + e) / 2;
        boolean cur = target[mid];
        //중간에 0이 나왔는데 현재 노드가 1이라면
        if (isEnd && cur) {
            result = 0;
            return;
        }
        //마지막 노드가 아닐 경우, 계속 진행
        if (s != e) {
            solve(s, mid-1, !cur);
            solve(mid+1, e, !cur);
        }
    }

    public int[] solution(long[] numbers) {
        int[] res = new int[numbers.length];
        for (int ind = 0; ind < numbers.length; ind++) {
            result = 1;
            long num = numbers[ind];
            //2진법 변환한 target 배열 생성
            //해당 수의 2진법 길이 계산
            int len = (int)Math.floor(Math.log(num) / Math.log(2)) + 1;
            //해당 수의 포화 이진트리 길이 계산
            int exp = 1;
            int treeLen = 0;
            while(true) {
                treeLen = (int)Math.pow(2, exp++) - 1;
                if (treeLen >= len) break;
            }

            target = new boolean[treeLen];
            int i = treeLen - 1;
            while(true) {
                long div = num / 2;
                long mod = num % 2;
                num = div;
                target[i--] = (mod == 1);
                if (div == 1) {
                    target[i] = true;
                    break;
                } else if (div == 0)
                    break;
            }
            solve(0, treeLen - 1, false);
            res[ind] = result;
        }
        return res;
    }
}