JAVA 프로그래머스 Lv.3 표현 가능한 이진트리

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

프로그래머스

 

 

---

문제

1.  표현이 가능한지 확인할 숫자가 들은 Long 배열 numbers ( 1 <= numbers.length <= 10000, 1 <= numbers[i] <= 10^10 )가 입력으로 들어옴.
2. 배열에 있는 숫자를 이진수로 바꾸어 이진 트리에 추가하여 해당 수를 판별하는데 이 때 숫자를 하나의 이진트리로 해당 수를 표현할 수 있다면 1을 결과 배열에 추가하고, 표현할 수 없다면 0을 결과 배열에 추가하여 return한다.

 

1. 배열에 있는 숫자를 이진수로 바꾸어 이진수가 포화 이진트리 (완전 이진트리)가 될 수 있도록 문자열 앞에 0을 추가한다.
2. 만들어진 문자열로 완전 이진트리를 만들어 부모가 0일 때 자식이 1인 경우가 있다면 표현할 수 없음을 나타내는 0을 결과 배열에 추가하고 아니라면 1을 추가해주면 된다.

---

 

 

초기 코드

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

        for (int i = 0; i < numbers.length; i++) {
            boolean flag = true;
            int num = 0;
            String binary = Long.toBinaryString(numbers[i]);
            int length = binary.length();

            for (int j = 0; true; j++) {
                num += (int) Math.pow(2, j);
                if (length == num) {
                    break;
                }
                if (num - Math.pow(2, j) < length &&
                        length < num) {
                    for (int k = 0; k < num - length; k++) {
                        binary = "0".concat(binary);
                    }
                    break;
                }
            }

            int count = 0;
            for (int j = 1; j < binary.length() - 1; j += 2) {
                if (j % 2 == 1 && binary.charAt(j) == '0' &&
                        (binary.charAt(j - 1) == '1' || binary.charAt(j + 1) == '1')) {
                    count++;
                }
            }

            for (int j = 2; j < binary.length() - 1; j++) {
                if ((int) Math.pow(2, j) + (int) Math.pow(2, (j - 1)) >= binary.length()) {
                    break;
                }

                if (binary.charAt((int) Math.pow(2, j))-1 == '1'
                        && binary.charAt((int) Math.pow(2, j) - (int) Math.pow(2, (j - 1))-1) == '1'
                        && binary.charAt((int) Math.pow(2, j) + (int) Math.pow(2, (j - 1))-1) == '1') {
                   
                    count--;
                }
            }


            if (count==0) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }

        return answer;
    }
}

 

절반정도 맞은 코드

예제 테스트 케이스와 질문하기에 있는 테스트 케이스는 모두 맞았다.

 

문자열을 따로 트리로 구성하진 않았고 문자열에서 해당 문자의 인덱스를 기준으로 문제를 풀어보기로 했다.

 

 

숫자를 이진수로 변경할 때는 트리의 노드 수가 트리 레벨에 따라 2의 제곱수로 증가함을 알아냈고, 이 점을 이용하여 숫자를 이진수로 변경한 문자열 앞에 0을 추가해주었다.

트리의 총 노드 수는 2의 레벨 - 1 제곱을 모든 레벨만큼 더해주면 된다.

-> 루트 노드(레벨 1)는 2의 0제곱 = 1개,

레벨 2 노드까지의 수는 2의 1제곱 + 2의 0제곱,

레벨 3 노드까지의 수는 2의 2제곱 + 2의 1제곱 + 2의 0제곱이다.

총 노드 수에서 숫자를 이진수로 변경한 문자열의 길이만큼 뺀 후 앞에 0을 추가해주면 완전 이진트리로 만들 수 있는 이진수 문자가 만들어진다.

 

이 때 중요한 것은 이진법을 계산할 때 0을 문자열 뒤가 아니닌 앞에서 붙여야 된다는 것이다.

문자열 뒤에 0을 추가하면 수가 변하기 때문에 앞에 추가하는 것이 가장 중요하다.

 

 

밑에 코드는 틀린 계산이지만 설명을 일단 해보겠다.

 

먼저 가장 밑 레벨에 있는 수들은 모두 홀수번째이고 부모 노드는 모두 짝수번이기 때문에 이 점을 이용해보기로 했다.

먼저 짝수번일 때(문자열 인덱스 상 홀수) 해당 위치의 문자가 '0'일 때 자식 노드 = 해당 문자의 좌우 문자가 '1'이라면 부모가 더미 노드일 때 자식으로 일반 노드인 '1'을 가진 것이 되므로 해당 수의 횟수를 증가시킨다.

-> 여기서 횟수를 증가시키는 이유는 자식 노드가 홀수가 아닌 부모 노드 (마지막 레벨 노드인 리프 노드가 아닌 노드들) 이 있기 때문이다.

 

 

자식 노드가 홀수가 아닌 부모노드는 바로 밑 반복문에서 계산한다.

반복문은 1이 아닌 2부터 시작(1일 경우 가장 왼쪽 작은 트리를 계산하게 됨.)하며 문자열의 길이만큼 반복한다. (중간에 멈출 것이라 상관없음)

반복문 변수를 이용해 2의 변수 제곱에 있는 인덱스가 1일 때 (2의 변수 제곱 수 - (2 변수 -1 의 제곱 수))위치의 수가 1이라면 횟수를 다시 감소시켜주었다.

 

 

 

여기서 왜 틀렸는지 분석을 해보니 2번 반복문에서  가장 왼쪽 부모들만 다시 계산이 되는 거여서 해결할 방법이 필요했다.

해결 방법을 생각해봤을 때 재귀함수를 이용해서 해결해야 될 것 같았다.

 

전체 노드를 2로 나누면 부모 노드의 위치가 나오고, 이 수를 이용해 자식 노드를 구하여 계산하면 될 것 같다.

조건은 똑같이 부모 노드가 0일 때 자식 노드가 1이라면 재귀를 중단하고 0을 결과 배열에 추가하고, mid가 1보다 작아질 때 = 0이 된다면 완전 이진트리가 된 것으므로 1을 배열에 추가하도록 한다.

 

재귀 함수의 재귀 부분에 들어갈 매개변수는 프로그래머스 질문하기에 있는 코드를 참고했다.

count라는 매개변수에 트리의 레벨을 넣어 부모 노드를 이용해 자식 노드 두 개를 구해 이진 트리의 결과를 구했다.

부모 노드가 0일 때만 자식 노드가 1인 경우에 결과를 false로 만들어주었다.

 

 

 

최종 코드

class Solution {
    public static boolean flag;

    public static void calculate(String binary, int s, int e, int size, int count) {
        int mid = size / 2;

        if (mid == 0) {
            return;
        }

        if (binary.charAt(s + mid) == '0' && (binary.charAt((s + mid - (int) Math.pow(2, count))) == '1'
                || binary.charAt((s + mid + (int) Math.pow(2, count))) == '1')) {
            flag = false;
            return;
        }

        calculate(binary, s, e - 1 - mid, mid, count - 1);
        calculate(binary, s + 1 + mid, e, mid, count - 1);
    }
    
    public int[] solution(long[] numbers) {
      int[] answer = new int[numbers.length];

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

            int num = 0;
            String binary = Long.toBinaryString(numbers[i]);
            int length = binary.length();
            int count = 0;

            for (int j = 0; true; j++) {
                num += (int) Math.pow(2, j);
                count = j;
                if (length == num) {
                    break;
                }
                if (num - Math.pow(2, j) < length && length < num) {
                    for (int k = 0; k < num - length; k++) {
                        binary = "0".concat(binary);
                    }
                    break;
                }
            }

            calculate(binary, 0, binary.length() - 1, binary.length(), count - 1);

            if (flag) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }

        return answer;
    }
}