99클럽 코테 스터디 32일차 TIL [트리, 재귀]

- 오늘의 학습 키워드 : 트리, 재귀

[문제 이름 : 표현 가능한 이진트리 (프로그래머스 2023 카카오 기출문제, Lv 3)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/150367

내가 작성한 코드는 아래와 같다.

import java.util.*;

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

        for (int i = 0; i < numbers.length; i++) {
            // 숫자를 이진수로 변환
            String binary = Long.toBinaryString(numbers[i]);
            // 포화 이진트리 크기 계산
            int treeSize = getFullBinaryTreeSize(binary.length());
            // 이진수를 포화 이진트리 길이로 패딩
            String paddedBinary = padBinary(binary, treeSize);

            if (isValidTree(paddedBinary)) {
                // 유효한 이진트리로 표현 가능
                result[i] = 1;
            } else {
                // 표현 불가능
                result[i] = 0;
            }
        }

        return result;
    }

    // 포화 이진트리의 노드 개수 계산
    private int getFullBinaryTreeSize(int length) {
        int size = 1;
        while (size < length) {
            // 2^h - 1 형태
            size = size * 2 + 1;
        }
        return size;
    }

    // 이진수를 포화 이진트리 크기로 설정
    private String padBinary(String binary, int size) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size - binary.length(); i++) {
            sb.append("0"); // 앞에 0을 추가
        }
        sb.append(binary);
        return sb.toString();
    }

    // 이진트리가 유효한지 확인
    private boolean isValidTree(String binary) {
        return checkTree(binary, 0, binary.length() - 1);
    }

    // 트리 유효성 검사
    private boolean checkTree(String binary, int start, int end) {
        if (start > end) return true; // 리프 노드까지 확인 완료

        int mid = (start + end) / 2; // 루트 노드
        char root = binary.charAt(mid);

        // 루트가 0인데 서브트리에 1이 존재하면 유효하지 않음
        if (root == '0') {
            for (int i = start; i <= end; i++) {
                if (binary.charAt(i) == '1') return false;
            }
        }

        // 왼쪽과 오른쪽 서브트리도 검사
        return checkTree(binary, start, mid - 1) && checkTree(binary, mid + 1, end);
    }
}

풀이 과정(풀이 시간 : 1시간)

카카오 문제는 항상 프로그래머스에서 풀기가 까다로운 것 같다 ㅠㅠ 코드가 길다보니 생각이 이어지기가 힘들고 구현 과정에서 애를 먹었다.

1. Long.toBinaryString으로 이진수로 변환한 다음, getFullBinaryTreeSize() 메서드로 주어진 이진수 길이보다 크거나 같은 가장 작은 포화 이진트리의 크기를 계산한다. (포화 이진트리의 크기는 2^h-1에 해당한다.)

2. padBinary() 메서드를 통해 이진수를 포화 이진트리 크기에 맞춰 앞에 0을 추가하여 맞춘다.

3. isValidTree() 메서드로 루트 노드와 서브트리의 유효성을 재귀적으로 검사한다. 이때, checkTree에서 중간 노드를 기준으로 왼쪽, 오른쪽 서브트리를 분할하여 검사한다.

내일은 다음주 화요일에 있을 기업 면접을 준비할 예정이다.