[Algorithm] 프로그래머스 - 표현 가능한 이진트리 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 표현 가능한 이진트리 자바 풀이를 작성하고자 합니다.

 

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/150367

프로그래머스

 

 

1. 풀이 소스

 

class Solution {
    
    int possible;
    
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        
        for (int k = 0; k < answer.length; k++) {
            String binaryNum = Long.toBinaryString(numbers[k]); // 숫자를 바이너리 이진 문자열로 변경 toBinaryString()
            
            int fullTreeLen = 0;
            int h = 1; // 포화 이진트리를 만들기 위한 높이
            
            while (fullTreeLen < binaryNum.length()) {
                fullTreeLen = (int) Math.pow(2, h++) - 1;
            }
            
            boolean[] isOne = new boolean[fullTreeLen]; // 포화 이진 트리를 생성하기 위한 배열
            
            // 참조#1
            int notDummyIdx = isOne.length - binaryNum.length(); // 더미 문자열이 아닌 인덱스
            for (int i = 0; i < binaryNum.length(); i++) {
                isOne[notDummyIdx++] = binaryNum.charAt(i) == '1'; // 더미 문자열이 아닌 인덱스부터 대응되는 인덱스의 문자열이 1인지 판단 
            }
            
            possible = 1; // 정답 초기화
            dfs(0, isOne.length - 1, false, isOne); 
            answer[k] = possible;
            
        }
        return answer;
    }
    
    void dfs(int start, int end, boolean isParentZero, boolean[] isOne) {
        if (possible == 0) return;
        
        int mid = (start + end) / 2; // 포화 이진 트리에서 부모 노드는 자식 노드의 위치의 중간

        if(isParentZero && isOne[mid]) { // 만약 부모가 zero인데, 해당 자식 노드가 1이라면 유효성 X
            possible = 0;
            return; // 종료
        }

        if(start != end) { // 참조#2
            dfs(start, mid - 1, !isOne[mid], isOne); // !fullTree[mid] -> 만약 1이었다면 true 이므로 false
            dfs(mid + 1, end, !isOne[mid], isOne); // 만약 0이었다면 false -> true 즉 부모가 0이므로 자식 노트가 1이 된다면 유효성 X
        }

    }
}

// 문제 해결 방안
// 1. 이진 스트링으로 만들기
// 2. 포화 이진트리로 만들기
// 3. 각 노드가 부모노드가 된다고 가정할 때, 부모노드가 0이라면 자식 노드 1을 가질 수 없으므로 유효성 판단

 

 

2. 풀이 중점 사항

 

문제 풀이 순서는 다음과 같습니다.

-  이진 스트링으로 만들기

-  포화 이진트리로 만들기

-  포화 이진트리로 생성하는 과정에서 이진 문자열을  다시 숫자로 변경한다고 생각할 때, 값이 변경되지 않는 선에서 앞에 0을 여러 개 추가할 수 있습니다. (포화 이진트리 개수 내로)

-  각 노드가 부모노드가 된다고 가정할 때, 부모 노드가 0이라면 자식 노드 1을 가질 수 없으므로 유효성을 판단하기

 

 

이진 스트링으로 변경하기

 

 String binaryNum = Long.toBinaryString(numbers[k]); // 숫자를 바이너리 이진 문자열로 변경 toBinaryString()

 

포화 이진트리로 만들기

 

int fullTreeLen = 0;
int h = 1; // 포화 이진트리를 만들기 위한 높이

while (fullTreeLen < binaryNum.length()) {
    fullTreeLen = (int) Math.pow(2, h++) - 1;
}

 

포화 이진트리는 노드의 개수가 2^h - 1입니다. 따라서, 이진 스트링으로 설정된 문자열의 개수가 포화 이진트리에 해당할 때까지, 반목문으로 fullTreeLen의 개수를 설정합니다.

 

 

참조 #1

 

// 참조#1
int notDummyIdx = isOne.length - binaryNum.length(); // 더미 문자열이 아닌 인덱스
for (int i = 0; i < binaryNum.length(); i++) {
    isOne[notDummyIdx++] = binaryNum.charAt(i) == '1'; // 더미 문자열이 아닌 인덱스부터 대응되는 인덱스의 문자열이 1인지 판단 
}

 

만약 문자열이 101010 (42) 이라고 가정하겠습니다.

해당 문자열의 값을 바꾸지 않는 선에서 포화 이진트리를 만들려면 0101010 이렇게 만들 수 있습니다.

 

//           1
//        1      1
//      0   0  0   0

 

여기서 더미 문자열이 아닌 인덱스 notDummyIdx란 실제 이진 문자열에서 유효한 0, 1이 아닌, 앞에 추가될 0의 개수를 의미합니다. isOne 배열은 포화 이진트리 개수로 선언된 boolean 배열이므로 만약 이진 스트링의 특정 위치의 값이 1이 아닌 경우 모두 false로 설정합니다.

 

참조 #2

 

앞 서 1 : true, 0 : false로 설정한 이유는 다음과 같습니다.

값을 변경하지 않는 선에서 포화 이진 트리를 구성하기 위해서는 부모 노드가 1인 경우 자식 노드를 0으로 추가하여 만들 수 있습니다. 하지만 부모 노드가 0 임에도 자식 노드가 1인 값이 존재한다면, 이는 유효한 경우가 아닙니다.

 

// 95

// 1011111
//             1
//           0    1
//         1  1  1  1 

// 42
// 010101
//           1
//         1   1
//        0 0 0 0

 

예를 들어, 1(노드)을 연결하여 이진 트리를 생성한 후, 빈 공간에 0을 삽입하여 포화 이진트리를 생성해야 하는데,
부모노드가 0이고 자식 노드가 1이라면, 이는 하나로 연결된 트리를 만들 수 없습니다.

따라서, 부모 노드가 0인 경우에 자식 노드가 1인 경우를 찾아서 하나라도 있다면 0을 리턴하면 됩니다.

그 외에는 모두 더미 노드로 0을 채워 넣을 수 있으므로 포화 이진트리로 요구하는 숫자를 완성시킬 수 있습니다.

 

    void dfs(int start, int end, boolean isParentZero, boolean[] isOne) {
        if (possible == 0) return;
        
        int mid = (start + end) / 2; // 포화 이진 트리에서 부모 노드는 자식 노드의 위치의 중간

        if(isParentZero && isOne[mid]) { // 만약 부모가 zero인데, 해당 자식 노드가 1이라면 유효성 X
            possible = 0;
            return; // 종료
        }

        if(start != end) { // 참조#2
            dfs(start, mid - 1, !isOne[mid], isOne); // !fullTree[mid] -> 만약 1이었다면 true 이므로 false
            dfs(mid + 1, end, !isOne[mid], isOne); // 만약 0이었다면 false -> true 즉 부모가 0이므로 자식 노트가 1이 된다면 유효성 X
        }

    }

 

부모 노드를 찾기 위해 자식 노드들의 위치의 중간 인덱스를 찾은 후, start, end가 다르다면 (계속 좁혀가기 때문에 결국 하나로 수렴하게 됨) 부모 노드의 자식 노드를 탐색하여 1 여부를 판단합니다.

!isOne [mid]는 만약 mid 인덱스에 속해있는 값이 1이라면 isOne[mid]는 true입니다.

다음 노드들은 0 혹은 1이어도 상관없으므로 false를 리턴하여 
if (isParentZero && isOne[mid]에 걸리지 않습니다.

 

반면, 0이라면, isOne[mid]는 false가 되고, !isOne[mid]가 true가 되므로,
parent가 0이면서, 자식 노드의 값이 1이라면 possible = 0이 되어 리턴됩니다.

 

 

이상으로 표현 가능 이진트리에 대한 설명을 마치도록 하겠습니다.

감사합니다!