[프로그래머스] Lv.3 표현 가능한 이진트리 문제 해결 과정(Java)

 문제 링크

---

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

프로그래머스

 

 

 

 해결 과정(힌트)

---

 이 문제를 해결하기 위해서 가장 먼저 주어진 10진수를 2진수로 변환된 이진트리로 표현해야 하는 절차를 거쳐야 합니다. 그래서 long형 변수를 Long.toBinaryString() 메서드를 사용했습니다. 

Long.toBinaryString(number);

 하지만 이렇게 되면 문자열의 길이를 최소로 하여 이진수를 표현하게 됩니다. 예시를 들어보겠습니다. 42를 toBinaryString() 메서드에 적용하면 "101010"이 됩니다. 이 문자열만 놓고 보면 이진트리로 표현이 불가능하지만 제일 앞쪽에 0을 붙이게 되면 "0101010"이 되어 높이가 2인 이진트리로 표현이 가능합니다.

 즉, 정수를 있는 그대로 적용하지 않고 값을 유지시키는 선에서 제일 앞쪽에 0을 붙여서 포화 이진트리의 형태로 만들어야 합니다.

 포화 이진트리
 이진트리의 구조에서 모든 노드의 차수(자식 노드의 개수)가 0 또는 2인 트리를 의미합니다.

포화 이진트리는 높이가 n일 때, 2^n - 1개의 노드를 갖는 특징이 있습니다.

 

 이렇게 변형한 문자열을 가지고 이제 해당 포화 이진트리가 유효한 이진트리인지 탐색을 해야 합니다. 보통 트리에서 탐색은 루트 노드부터 시작합니다. 루트 노드는 어떤 경우에서든 간에 변형된 문자열에서 중간에 있는 글자입니다. 그래서 중간의 글자부터 탐색을 시작합니다. 탐색과정은 이렇게 되어야 합니다.

• 현재 위치에 있는 노드가 1이면, 진짜 노드이므로 해당 노드의 자식 노드를 탐색합니다.
• 현재 위치에 있는 노드가 0이면, 가짜 노드이므로 해당 노드의 서브 트리에 진짜 노드가 있는지 확인합니다.

 저는 dfs와 binarySearch로 탐색 과정을 수행했습니다.

실행 결과

 

 전체 코드

---

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i = 0; i < answer.length; i++) {
            answer[i] = isTree(numbers[i]);
        }
        return answer;
    }
    
    private int getHeight(String str) {
        int n = 0;
        int length = str.length();
        while(length >= Math.pow(2, n)) {
            n++;
        }
        return n;
    }
    
    private int getNodeCount(String str) {
        return (int) Math.pow(2, getHeight(str)) - 1;
    }
    
    private int isTree(long number) {
        StringBuilder sb = new StringBuilder();
        sb.append(Long.toBinaryString(number));
        int count = getNodeCount(sb.toString());
        for(int c = sb.toString().length(); c < count; c++) {
            sb.insert(0, "0");
        }
        String tree = sb.toString();
        
        return dfs(tree, 0, count);
    }
    //dfs + binarySearch
    private int dfs(String tree, int start, int end) {
        if(end - start == 1) return 1;
        
        int mid = (end + start) / 2;
        if(tree.charAt(mid) == '0') {
            //만약 서브 트리의 시작 인덱스가 0이 아니면, 1만큼 증가시킨다.
            int subStart = start;
            if(start != 0) subStart++;
            //서브트리에 진짜 노드가 있으면 0을 반환한다.
            for(int s = subStart; s < end; s++) {
                if(tree.charAt(s) == '1') return 0;
            }
        }
        
        int left = dfs(tree, start, mid);
        int right = dfs(tree, mid, end);
        return left == 1 && right == 1 ? 1 : 0;
    }
}

 

 

 정리

---

• 트리 탐색은 bfs보다 dfs에서 효율이 좋음.