[Programmers] 표현 가능한 이진트리 (Java)

1. 문제요약

코딩테스트 연습 - 표현 가능한 이진트리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

아래 과정을 수행해서 만들어지는 숫자를 포화 이진 트리로 표현 가능한 숫자라고 가정한다.

 

1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.

 

반대로 숫자가 주어질 때, 포화 이진 트리로 표현 가능한지 구하시오.

 

2. 문제예제

문제 지문에 잘 나와있으므로 생략한다.

 

3. 팩트추출

Fact 1 : 문제에서 이야기하는 표현 가능한 이진트리는 트리 중앙에 있는 부모 노드의 값이 항상 있어야 한다는 특징을 가지고 있다. 그래서 중앙에 값이 있는지 체크하기 위해 포화 이진 트리 크기로 배열을 늘리고 중앙에 값이 있는지 재귀로 호출하면서 체크해야 한다. 전체 과정을 수행하기 위한 처리 루틴은 다음과 같다.

 

1. 숫자를 이진수로 바꾸었을 때, 이진수 자릿수를 구한다.
2. 이진수 자릿수를 포화 이진 트리 노드의 갯수만큼 늘린다.
3. 늘린 자릿수만큼 배열을 할당하고, 남은 앞 부분은 0 더미로 채운다.
4. 재귀로 호출하면서 트리의 서브트리 중앙 노드 값들을 값이 있는지 체크한다.

 

Fact 2 : 이진수로 표현했을 때 자릿수를 구하려면 중학교 때 배운 기수법과 로그의 성질을 이해해야 한다.

 

 

 

최종 m 번째 숫자가 결국 n 진법으로 나타냈을 때 자릿수와 같다. m * (n 진법 ^ m-1)

이 m 을 구하기 위해 log 를 활용하면 logn(10진수 숫자) + 1 이 된다. 

 

 

Fact 3 : 이진수 자릿수를 포화 이진 트리 노드의 갯수만큼 늘리려면 포화 이진 트리 노드의 갯수 공식을 알아야 한다.

트리 높이에 따라 포화 이진 트리 노드의 갯수를 구해보면 1, 3, 7, 15 ... 와 같은 수열임을 확인할 수있고, 이는  2^n-1 인 수식으로 표현이 가능하다. 즉, 이진수 자릿수보다 같거나 한 단계 큰 포화 이진 트리 노드의 갯수를 구하면 된다.

 

4. 문제전략

Fact 2 + Fact 3 공식과 DFS 로 트리를 절반씩 순회하면서 중앙에 있는 값이 0 인지 체크하면 된다. 

 

5. 소스코드

class Solution {
    public int treeLength;
    public int result;
    
    public void validateBinaryTree(boolean[] target, int start, int end, boolean isEnd) {
        int mid = (start + end) / 2;
        boolean current = target[mid];
        if (isEnd && current) {
            result = 0;
            return;
        }
        if (start != end) {
            validateBinaryTree(target, start, mid-1, !current);
            validateBinaryTree(target, mid+1, end, !current);
        }
    }

    private boolean[] makeTarget(long number) {
        int binaryLength = (int) Math.floor(Math.log(number) / Math.log(2)) + 1;

        int treeHeight = 1;
        treeLength = 0;
        while (treeLength < binaryLength) {
            treeLength = (int) Math.pow(2, treeHeight++) - 1;
        }

        boolean[] target = new boolean[treeLength];
        int i = treeLength - 1;
        while(true) {
            long div = number / 2;
            long mod = number % 2;
            number = div;
            target[i--] = (mod == 1);
            if (div == 1) {
                target[i] = true;
                break;
            } else if (div == 0) {
                break;
            }
        }
        return target;
    }
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        for (int i = 0; i < numbers.length ; i++) {
            result = 1;
            boolean[] target = makeTarget(numbers[i]);
            validateBinaryTree(target, 0, treeLength-1, false);
            answer[i] = result;
        }
        return answer;
    }
}