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

문제 바로가기

프로그래머스

 

[문제 풀이]

먼저, 포화 이진트리를 만들어야한다.

 

포화 이진트리의 노드 개수는 항상 [2 ^ N - 1] 개이다.

그렇기 때문에 주어진 숫자를 2진수로 나타날때 2진수의 길이 또한 [2 ^ N - 1]개이다.

만약 8이라는 숫자가 주어진다면, 8은 이진수로 1000 이다.

1000의 길이는 4이므로 [2 ^ N -1]개가 아니다.  [2 ^ N -1]개를 충족하며 가장 짧은 길이를 구한다면

[2 ^ 3 - 1]개이다. 이는 7개이다. 이제 1000을 7개의 값을 가진 이진수로 만든다면 0001000 으로 만들 수 있다.

 

포화 이진트리를 만들었으니 이제 할 것은 부모 노드와 자식 노드 2개를 체크하는 것이다.

무엇을 체크 할거냐면, 자식 노드가 더미 노드가 아닌데 부모 노드가 더미 노드인지 체크하는 것이다.

 

이때, 부모 노드와 자식 노드 그리고 리프 노드를 구분해야한다.

한 가지 규칙을 발견하자면 리프 노드의 번호는 항상 홀수이다.

그래서 리프노드로 가는 과정에서 체크를 하고, 리프노드로 가고 나서도 체크를 하고 반환을 하면 문제를 풀 수 있다.

 

여기서 주목해야하는 것은 각 노드의 번호이다. 그림을 그려보는 것을 추천한다.

번호를 잘 살펴보면 루트 노드를 어떻게 구하고 자식 노드를 어떻게 구하는지는 매우 쉽게 발견할 수 있다고 생각한다.

그리고 리프 노드는 홀수라고 했으니 리프 노드에서 반환하면 문제를 풀 수 있다.

 

[코드]

import java.util.Arrays; class Solution {     static StringBuilder sb; //포화 이진트리를 저장     public int[] solution(long[] numbers) {         int[] answer = new int[numbers.length];         for (int i = 0; i < numbers.length; i++) {             if (check1(numbers[i])) answer[i] = 0;             else answer[i] = 1;         }         return answer;     }     public boolean check1(long A) {         String aa = Long.toString(A, 2); //10진수 -> 2진수         int temp = 1;         while (Math.pow(2, temp) - 1 < aa.length()) temp++; // [2 ^ N -1]개에서 N을 구하는 과정         // [2 ^ N -1]개의 이진수를 만드는 과정         sb = new StringBuilder();         for (long i = 0; i < Math.pow(2, temp) - 1 - aa.length(); i++) {             sb.append("0");         }         sb.append(aa);         // 루트 노드의 번호         int root = sb.length() / 2 + 1;                  // 부모 노드와 자식 노드를 체크         return check(root, root + root / 2, root / 2) || check(root, root - root / 2, root / 2);     }     public boolean check(int root, int child, int depth) {         // 만약 리프 노드에 도달 하였다면, 더미 노드 체크         if (child % 2 == 1) {             if (sb.charAt(root - 1) == '0' && (sb.charAt(root - 2) == '1' || sb.charAt(root) == '1')) return true;             else return false;         }         // 리프 노드에 가는 과정에서, 더미 노드를 체크         if (sb.charAt(root - 1) == '0' && (sb.charAt(root - 1 - depth) == '1' || sb.charAt(root - 1 + depth) == '1'))             return true;         // 부모 노드에서 자식 노드를 체크하고 나서,         // 자식 노드를 부모 노드로 설정하고, 자식 노드의 자식을 체크한다.         return check(root - depth, child - depth / 2, depth / 2) || check(root + depth, child + depth / 2, depth / 2)                 || check(root - depth, child + depth / 2, depth / 2) || check(root + depth, child - depth / 2, depth / 2);     } }