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

🔎 문제 설명

표현 가능한 이진트리 문제

💡 풀이 방식

문제 설명이 너무 어렵게 되어있어서 질문하기 페이지에 다른 분들이 남겨주신 설명들을 많이 참고했다.

쉽게말해 포화이진트리를 만들어서 중위순회로 이진수를 만들 수 있는가에 대한 문제인 것 같다.

핵심 포인트는 부모가 0일때 자식이 있으면 안된다는 것이다.
부모가 0일때 자식이 0인 더미노드들로 구성되어 있다면 가능하지만 0인 부모 밑에 1인 자식이 있으면 불가능!

계속해서 오류가 발생할 때는 이 부분을 잘 확인해보자

1. 먼저 주어진 숫자를 이진수로 변환하기
여기서 포인트는 추가해야 할 0의 개수
포화 이진트리를 만들기 위해 만들어야 할 트리의 높이를 계산하여 부족한 0의 개수를 채워주었다.

//포화이진트리 만들기 위해 추가해야하는 0의 개수
    private int zeroCount(int length){

        int len = length;
        int level = 1;
        while(len > 0){
            len -= level;
            level *= 2;
        }
        return Math.abs(len);

    }

2. 깊이 우선 탐색 수행하기
트리의 루트를 기준으로 왼쪽 오른쪽으로 나누어 탐색한다.

3. 재귀를 수행하며 부모의 더미 여부 파악하기
현재 수행하고 있는 트리의 루트가 0이면 다음 재귀로 넘어갈 때 더미 변수에 true값을 부여하여 넘겨주었다.
더미 값이 참일 때 현재 루트값이 1이면 이진트리 표현 불가능!

if(binary[rootIdx] == 1 && dummy) { //부모가 0일때 자식이 1이면 안됨
	result = 0;
	return;
}

💻 전체 정답 코드

import java.util.*;
class Solution {
    static int result;
    int[] binary;
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];

        for(int i=0; i<numbers.length; i++){
            binary = changeToBinary(numbers[i]);
            result = 1;
            dfs(0,  binary.length - 1, false);
            answer[i] = result;
        }

        return answer;
    }

    private void dfs(int startIdx, int lastIdx, boolean dummy){
        int rootIdx = (startIdx + lastIdx) / 2;
        
        if(binary[rootIdx] == 1 && dummy) {
            result = 0;
            return;

        }

        if(startIdx != lastIdx){
            if(binary[rootIdx] == 0) dummy = true;
            else dummy = false;
            dfs(startIdx, rootIdx -1, dummy);
            dfs(rootIdx + 1, lastIdx, dummy);
        }



    }

    private int[] changeToBinary(long number){

        ArrayList<Integer> list = new ArrayList<>();
        long n = number;
        while(n > 1){
            list.add(0, (int)n%2);
            n /= 2;
        }
        list.add(0, (int)n);

        //포화이진트리가 아니면 0 추가
        int addZero = zeroCount(list.size());
        if(addZero != 0){
            for(int i=0; i<addZero; i++)
                list.add(0, 0);
        }
        return list.stream().mapToInt(i -> i).toArray();

    }

    private int zeroCount(int length){

        int len = length;
        int level = 1;
        while(len > 0){
            len -= level;
            level *= 2;
        }
        return Math.abs(len);

    }
    
}