프로그래머스 Level3 표현 가능한 이진트리 (Java)

• https://school.programmers.co.kr/learn/courses/30/lessons/150367
• 문제
  • 이진트리를 수로 표현한다. 표현방법은 다음과 같다.
    1. 이진수를 저장할 빈 문자열을 생성합니다.
    2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
    3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
    4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
    5. 문자열에 저장된 이진수를 십진수로 변환합니다.
  • 이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.
  • 수가 주어졌을 때 이진트리로 해당 수를 표현가능한지 여부를 반환하라.
• 제한사항
  • 1 ≤ numbers의 길이 ≤ 10,000
  • 1 ≤ numbers의 원소 ≤ 10^15
• 코드

public class Solution {
	private static int[] answer;
	private static boolean dfs(String number) {
		boolean valid = true;
		
		int mid = (number.length()-1)/2;
		char root = number.charAt(mid);
		String left = number.substring(0,mid);
		String right = number.substring(mid+1,number.length());
		
		if(root == '0' && (left.charAt((left.length()-1)/2)=='1' || right.charAt((right.length()-1)/2)=='1')){
			return false;
		}
		
		if(left.length() >= 3) {
			valid = dfs(left);
			if(valid) {
				valid = dfs(right);
			}
		}
		return valid;
	}
    public int[] solution(long[] numbers) {
        answer = new int [numbers.length];
        
        for(int i = 0; i < numbers.length; i++) {
        	String cur = Long.toBinaryString(numbers[i]);
        	int j = 0;
        	while((int)Math.pow(2, j)-1 < cur.length()) {
        		j++;
        	}
        	while((int)Math.pow(2, j)-1 != cur.length()) {
        		cur = "0"+ cur;
        	}
        	if(dfs(cur)) {
        		answer[i] = 1;
        	}
        }
        return answer;
    }
}

• 풀이
  • 이진트리의 서칭을 물어보는 문제다. 완전탐색으로 서칭을 하면 된다.
  • 탐색을 하기 전 포화이진트리로 만들어야 한다.
    • 포화이진트리의 전체크기는 2^h-1이다. 따라서 h를 0부터 늘여가면서 주어진 길이보다 더 큰 포화 이진트리의 크기를 구한 후 차이만큼 0을 왼쪽에 덧붙인다.
    • 왼쪽에 붙이는 이유는 오른쪽에 붙이면 이진수이기 때문에 값이 달라진다. 따라서 왼쪽에 붙여야 한다.
  • 결국 비교하는 것은 root, 왼쪽 서브트리의 root, 오른쪽 서브트리의 root 3개이다. 또한 root이 0이고, 오른쪽이나 왼쪽 서브트리의 root이 0이 아니면 해당 수는 이진트리로 표현할 수 없다.
  • root의 경우 항상 가운데에 위치한다.
    • root의 Index = (문자열의 길이 -1)/2