[2023 KAKAO BLIND RECRUITMENT] 표현 가능한 이진트리

최민길(Gale)·2023년 2월 27일
1

알고리즘

목록 보기
44/172

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150367

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 문제의 조건을 재귀함수를 이용하여 탐색하여 풀 수 있습니다. 문제에서 구현해야 하는 부분은 크게 2가지 입니다.

  1. 현재 수(10진수)를 포화 이진 트리로 치환 가능한 이진수로 변경하기
  2. 구한 이진수가 포화 이진 트리로 치환 가능한지 체크하기

첫 번째 부분의 경우는 포화 이진 트리의 특징을 이용하여 진행할 수 있습니다. 포화 이진 트리의 크기는 2^n - 1 이기 때문에 주어진 수를 이진수로 변환했을 때 자리수가 더 커질 때까지 n값을 증가시킵니다. 그 후 이진수의 길이와 포화 이진 트리의 크기가 같아질 때까지 이진수의 앞에 0을 추가합니다.

두 번째 부분 역시 포화 이진 트리의 특징을 이용하여 진행할 수 있습니다. 루트 노드의 경우 문자열 길이의 가운데에 위치해있는 것을 알 수 있습니다. 이 때 루트 노드에서 비교할 자식 노드들은 다시 자식 노드를 이루고 있는 문자열의 가운데에 위치해있습니다. 따라서 루트 노드와 각각 왼쪽과 오른쪽 두 개의 서브 노드끼리 비교합니다. 이 때 루트 노드가 0인데 자식 노드가 1일 경우 성립할 수 없으므로 false를 리턴, 그 외의 경우는 자식 노드의 문자열 길이가 3보다 작아질 때까지 재귀함수로 계속 절반씩 나누어 비교하는 방식으로 진행합니다.

여기서 제약 조건을 다시 살펴보겠습니다. 각 원소의 크기는 10^15 이하입니다. 위의 로직대로라면 주의해서 보아야 할 것은 자리수이기 때문에, 10^15 < 16^15 = 2^60, 즉 자리수는 대략 계산해보아도 60자리를 넘지 않기 때문에 자리수 값은 int로 설정 가능합니다.

코드를 보여드리기 전에 하나 의문점이 있어 이 부분은 조금 더 공부해보려고 합니다. 왼쪽의 자식 노드의 값과 오른쪽의 자식 노드의 값을 char로 저장한 후 실행하면 런타임 에러가 나타나는데, 이 부분을 저장하지 않고 if문 내부에 그대로 사용할 경우 통과되는 것을 확인하였습니다. 이 부분의 원인이 무엇인지 조금 더 살펴봐야 할 것 같습니다.

다음은 코드입니다.

class Solution {
    static boolean isValidNum(String binary){
        // 루트 노드의 경우 문자열 길이의 한 가운데
        int mid = (binary.length()-1)/2;
        char root = binary.charAt(mid);
        // 루트 노드의 자식 노드는 가운데 기준 왼쪽 수의 가운데 수와 오른쪽 수의 가운데 수
        String left = binary.substring(0,mid);
//        char leftSubRoot = left.charAt((left.length()-1)/2);

        String right = binary.substring(mid+1,binary.length());
//        char rightSubRoot = right.charAt((right.length()-1)/2);

        // 루트 노드는 0인데 자식 노드가 1일 경우는 false
//        if(root=='0' && (leftSubRoot=='1' || rightSubRoot=='1')) return false;
        if(root=='0' && (left.charAt((left.length()-1)/2)=='1' || right.charAt((right.length()-1)/2)=='1')) return false;

        // 그 외의 경우는 왼쪽 수와 오른쪽 수를 재귀 실행
        // 이 때 왼쪽 수의 크기가 3보다 작을 경우 리프 노드에 도달했으므로 비교하지 않음
        boolean result = true;
        if(left.length() >= 3){
            // 왼쪽 실행 결과가 true라면 오른쪽 실행
            result = isValidNum(left);
            if(result) result = isValidNum(right);
        }
        // 오른쪽 실행 결과 리턴
        return result;
    }

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

        // 포화 이진 트리 만들기
        for(int i=0;i<numbers.length;i++){
            // 1. 현재 수를 이진수로 변환
            String binary = Long.toBinaryString(numbers[i]);

            // 2. 포화 이진 트리의 크기는 2^n - 1 이기 때문에 현재 구한 이진수의 n값을 구하기
            int exponent = 0;
            while((int)Math.pow(2,exponent)-1 < binary.length()){
                exponent++;
            }

            // 3. 현재 길이와 포화 이진 트리의 크기와 다르다면 앞에 0 추가
            while((int)Math.pow(2,exponent)-1 != binary.length()){
                binary = "0" + binary;
            }

            // 만약 이진수가 포화 이진 트리로 표현 가능하다면 answer에 1 추가
            if(isValidNum(binary)) answer[i] = 1;
            else answer[i] = 0;
        }

        return answer;
    }
}

profile
저는 상황에 맞는 최적의 솔루션을 깊고 정확한 개념의 이해를 통한 다양한 방식으로 해결해오면서 지난 3년 동안 신규 서비스를 20만 회원 서비스로 성장시킨 Software Developer 최민길입니다.

0개의 댓글