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

문제

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

이진트리를 수로 표현하는 방법은 다음과 같습니다.

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

이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

다음은 이진트리를 수로 표현하는 예시입니다.

주어진 이진트리는 다음과 같습니다.

주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.

노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.

당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.

이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

---

접근

오랫동안 고민하다가 0을 추가하여 포화이진트리를 만들 생각을하니 문제가 해결되었습니다.

주어진 이진수로 포화이진트리를 만들어야하는데,

 

4.살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.

 

문제에 나와있는 4번이때문에 뭔가 헷갈렸습니다.

하지만 주어진 숫자에서 포화이진 트리를 만를려면 무조건 앞에 0을 추가하는 수밖에 없음 뒤에 넣거나 1을 넣게되면 값이 바뀌게 되기 때문입니다.

포화이진 트리를 만들었으면

왼쪽파트, 가운데, 오른쪽 파트를 나눠서 재귀를 돌면됩니다.

 

예를들어

50이라는 수가 있으면

이진수로

50 ⇒ 110010

포화이진트리로 만들어야 하므로(포화이진트리는 2**k-1이 자릿수가 될때까지 자릿수를 맞춰서 0을 넣으면됨)

110010 ⇒ 0110010

왼쪽: 011

가운데: 0

오른쪽: 010

이 경우, 왼쪽 오른쪽이 1을 포함하고 있는데 가운데 값이 0이라 0을 리턴합니다.

자식중에 1이 있으면 부모도 무조건 1이어야 하기 때문입니다.

---

코드

function solution(numbers) {
    var answer = [];
    //반환값 [1이있는지, 정상적인 문자열인지]
    const search = (str) =>{
        if(str.length === 1){
            if(str[0] === '1') return [true,true];
            return [false,true];
        }
        let mid = parseInt(str.length/2);
        let left = search(str.slice(0,mid));
        let right = search(str.slice(mid+1));
        //왼쪽, 오른쪽이 모두 정상적인 문자열이 아니면 바로 실패
        if(left[1] && right[1]){
            //왼쪽오른쪽이 모두 1이 포함되어 있음, 따라서 가운데 값은 무조건 1이되야함.
            if(left[0] && right[0]){
                if(str[mid] === '1') return[true,true];
                else return[true,false];
            }
            //왼쪽 오른쪽 둘다 1이 포함안되어 있음, 따라서 다운데 값은 어떤값도 가능함
            else if(!left[0] && !right[0]){
                if(str[mid] === '1') return[true,true];
                else return [false, true];
            }
            //왼쪽 오른쪽 둘중 하나만 1이 포함된 경우, 가운데는 무조건 1이어야함.
            else{
                if(str[mid] === '1') return[true,true];
                else return [true,false];
            }
            
        }
        //실패
        else return [true,false];
        }
    
    for(let number of numbers){
        if(number===1){
            answer.push(1);
            continue;
        }
        let k = 0;
        let str = number.toString(2);
        while(2**k-1 < str.length){
            k++;
        }
        
        const startLen = str.length;
        for(let i=startLen; i<2**k-1; i++){
            str = '0' + str;
        }
        answer.push(search(str)[1]? 1:0);
    }
    return answer;
}

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        int index = 0;
        for(long number : numbers){
            StringBuilder sb = new StringBuilder();
            String str = Long.toBinaryString(number);
            int k = 0;
            while(str.length() > Math.pow(2,k)-1){
                k++;
            }
            int len = str.length();
            for(int i=len; i<Math.pow(2,k)-1; i++){
                sb.append("0");
            }
            sb.append(str);
            str = sb.toString();
            boolean[] result = search(str);
            if(result[1]) answer[index++] = 1;
            else answer[index++] = 0;
        }
        return answer;
    }
    public boolean[] search(String str){
        if(str.length() == 1){
            if(str.equals("1")) return new boolean[]{true,true};
            else return new boolean[]{false,true};
        }
        int mid = str.length()/2;
        boolean[] left = search(str.substring(0,mid));
        boolean[] right = search(str.substring(mid+1));
        if(left[1] && right[1]){
            if(left[0] && right[0]){
                if(str.charAt(mid) == '1') return new boolean[]{true,true};
                else return new boolean[]{true,false};
            }
            else if(!left[0] && !right[0]){
                if(str.charAt(mid) == '1') return new boolean[]{true,true};
                else return new boolean[]{false, true};
            }
            else{
                if(str.charAt(mid) == '1') return new boolean[]{true,true};
                else return new boolean[]{true,false};
            }
        }
        else{
            return new boolean[]{true,false};
        }
    }
}

---

주의

x