[2023 KAKAO BLIND RECRUITMENT] 표현 가능한 이진트리

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

문제 해결 전략

1. 주어진 수를 이진수로 변환하기
2. 만들어진 이진수를 "포화이진수"로 만들기
3. 만들어진 포화 이진수를 탐색하며 부모 노드, 자식 노드를 기록하기
4. 부모 노드의 값이 0이면서 자식 노드의 값이 1이라면 표현 가능한 이진트리가 아님!!

문제에서 가장 중요한 포인트는, 포화 이진수를 만드는 것과 각 노드들의 자식노드를 기록하는 것 입니다.

문제를 잘 분석해보면, 포화 이진수로 표현하기 위해서는 해당 "이진수의 길이" =  "2의 거듭제곱 - 1"임을 알 수 있습니다.

따라서 해결 전략 1에서 나온 이진수의 길이보다 큰 2의 거듭제곱을 찾고 그 값에 1을 뺀 길이 만큼 이진 수 앞에 '0'을 붙여 포화 이진수를 만듭니다.

 

//len 보다 큰 최소의 2의 거듭제곱의 값을 찾고 1뺀 값을 return
int findLength(int len){
    int x = 1;
    while(x <= len){
        x *= 2;
    }
    return x - 1;
}

for(int i=0; i<numbers.length; i++){

	String binary = Long.toString(numbers[i], 2);
	String saturatedBinary = "0".repeat(findLength(binary.length()) - binary.length()) + binary;
    
    //이후 로직...
}

 

이후 만들어진 포화 이진수로 각각의 노드에 대해서 자식 노드들을 기록합니다.

 

저는 DFS로 각 노드에서 왼쪽자식, 오른쪽 자식을 기록했습니다.

int dfs(int start, int end, int[][] child){

    if(start == end){
        return start;
    }

    int parent = (start + end) / 2;
    child[parent][0] = dfs(start, parent - 1, child);
    child[parent][1] = dfs(parent + 1, end, child);
    
    return parent;
}

 

위 함수가 반환하는 값은 start ~ end까지의 범위 중 root가 되는 노드의 값을 반환하며, 이때 재귀를 통해 왼쪽 자식과 오른쪽 자식을 기록합니다.

 

이후 각 노드에 대해 자식 노드들을 모두 기록했다면 Root 노드부터 탐색하기 시작하여 해당 포화 이진트리가 유효한지 검사합니다.

만약, 부모노드의 값이 '0'이면서, 자식노드의 값이 '1'이라면 해당 포화 이진트리는 유효하지 않은 트리입니다.

 

아래는 전체 코드입니다.

import java.util.*;

class Solution {

    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];

        for(int i=0; i<numbers.length; i++){
            String binary = Long.toString(numbers[i], 2);
            String saturatedBinary = "0".repeat(findLength(binary.length()) - binary.length()) + binary;
            answer[i] = solve(saturatedBinary) ? 1 : 0;
        }
        return answer;
    }

    boolean solve(String binary){
        int[][] child = new int[binary.length()][2];
        dfs(0, binary.length() - 1, child);
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add((binary.length() - 1) / 2);
        while(!queue.isEmpty()){

            int parent = queue.poll();
            //리프노드일때 continue
            if(Arrays.equals(child[parent], new int[]{0, 0})) continue;

            int left = child[parent][0]; //왼쪽 자식
            int right = child[parent][1]; //오른쪽 자식
            
            if(binary.charAt(parent) == '0' && (binary.charAt(left) == '1' || binary.charAt(right) == '1')) return false;
            queue.add(left);
            queue.add(right);
        }
        return true;
    }
	
    //부모노드의 자식노드 기록하기
    int dfs(int start, int end, int[][] child){

        if(start == end){
            return start;
        }

        int parent = (start + end) / 2;
        child[parent][0] = dfs(start, parent - 1, child);
        child[parent][1] = dfs(parent + 1, end, child);
        return parent;
    }

	//len 보다 큰 최소의 2의 거듭제곱의 값을 찾고 1뺀 값을 return
    int findLength(int len){
        int x = 1;
        while(x <= len){
            x *= 2;
        }
        return x - 1;
    }
}