[Algorithm] 프로그래머스 - 표현 가능한 이진 트리 (Java)

저번주 코테 스터디 문제인 2023 카카오 코테 중 하나인 표현 가능한 이진 트리의 풀이를 가지고 왔다.

문제는 아래 링크를 통해 확인해 주시면 될 것 같다.

표현 가능한 이진 트리

문제를 보고, 아 이건 이진 검색을 쓰면 되겠다 싶었다.

왼쪽 노드와 오른쪽 노드를 모두 검색해야 했기에 이진 검색 + 분할 정복 알고리즘을 사용하여 문제를 풀었다.

코드는 보고 싶지 않고 힌트만을 얻고 싶은 분들을 위해 설명부터 작성하겠다.

풀이 흐름

1. 10진수를 2진수 문자열로 변경
2. 만약 이진수가 모두 1일 경우는 1, 이진수가 0일 경우는 0을 result에 바로 삽입
3. 위의 조건이 아닌 경우 makeTree 함수를 만들어 완전이진트리가 될 때까지 이진수 앞에 0 추가
   • 현재 이진수의 길이보다 첫 번째로 큰 길이가 될 때까지 추가
   • 예를 들어 이진수가 11인 경우 완전이진트리로 만들려면 길이가 3이 되어야 하므로, 앞에 0 하나를 더 붙여 011로 만듦
4. isUnavailable 함수를 만들어 이진트리가 될 수 없으면 true, 될 수 있다면 false 출력
   • 이진 검색 알고리즘을 통해 root를 기준으로 양쪽을 검사
   • 분할 정복으로 모든 노드를 검사
   • 재귀 사용
   • 만약 루트가 0인데 양쪽 노드 중 하나라도 1이 있으면 이진트리가 될 수 없음
5. true/false에 따라 result에 값 삽입

위와 같은 흐름으로 진행됐다.

처음 풀 때 놓쳤던 부분이 두 가지 있다.

1. 완전이진트리가 될 때까지 앞에 0을 추가해줘야 하는 점
2. 단말노드가 아니고, 루트가 될 수 있는 노드 중 값이 0인 게 있다고 무조건 실패가 아닌 점

1번을 보완하기 위해 makeTree 함수를 만들었고, 2번을 보완하기 위해 isUnavailable 함수 중간에 조건문을 하나 추가했다.

주석으로도 달아놨지만, 2번은 입력 값이 8일 때 이진법 1000으로 표현되는데 완전이진트리로 변경 후 왼쪽과 오른쪽 노드를 살펴보면 루트가 0이라 무조건 true가 반환 됐었다.
양쪽 부분 트리의 루트가 0이지만, 나머지도 모두 더미 노드이기 때문에 완전이진트리가 될 수 있기에 false가 출력됐어야 했다.

코드는 아래와 같다.

import java.io.*;
import java.util.*;

class Solution {
    static int[] result;

    public static int[] solution(long[] numbers) {

        result = new int[numbers.length];

        for (int i = 0; i < numbers.length; i++) {
            StringBuilder sb = new StringBuilder();
            // 2진수 변환
            String binaryValue = Long.toBinaryString(numbers[i]);
            
            // 이진수가 모두 1로 구성되어 있다면 이진트리 가능
            if (!binaryValue.contains("0")) {
                result[i] = 1;
                continue;
            }
            // 만약 이진수 값이 0이라면 될 수 없으므로 바로 0 삽입
            if (binaryValue.length() == 1) {
                if (numbers[i] == 0) result[i] = 0;
                continue;
            } else{
            	// 위의 조건이 모두 아닐 경우 완전이진트리로 만듦
                binaryValue = makeTree(binaryValue);
            }
            sb.append(binaryValue);

            binaryValue = sb.toString();
		
        	// 완전이진트리로 만들 수 있는지 없는지 판별
            result[i] = isUnavailable(binaryValue, 0, binaryValue.length() - 1) ? 0 : 1;
        }

        return result;
    }

    public static boolean isUnavailable(String binaryValue, int start, int end) {
    	// 이진 검색을 끝냈다면 false 반환, 만들 수 있음
        if (start > end || start == end) {
            return false;
        }

		// 루트 설정
        int root = (start + end) / 2;

		// 루트가 0인 경우
        if (binaryValue.charAt(root) == '0') {
        	// start부터 end까지 1이 하나라도 있다면 완전이진트리 불가
            // 예를 들어, 입력값이 8인 경우 0001000로 표현됨
            // 0001000은 완전이진트리지만, 왼쪽과 오른쪽의 노드가 모두 0
            // 이런 경우를 방지하기 위한 for문
            for(int i = start; i <= end; i++) {
                if(binaryValue.charAt(i) == '1') return true;
            }
            // 모두 0이라면 false
            return false;
        }

		// 루트 기준 왼쪽 노드 이진 검색
        boolean left = isUnavailable(binaryValue, start, root - 1);

		// 루트 기준 오른쪽 노드 이진 검색
        boolean right = isUnavailable(binaryValue, root + 1, end);

		// 하나라도 true라면 true 반환
        return left || right;
    }

    public static String makeTree(String value){
        int treeLength = 1;
        // 완전이진트리의 길이 공식
        while(value.length() > treeLength){
            treeLength = treeLength * 2 + 1;
        }

		// 완전이진트리 길이 - 이진수의 길이
        int zeroLength = treeLength - value.length();
        StringBuilder sb = new StringBuilder();
        // 빼준 길이만큼 앞에 0 추가
        sb.append("0".repeat(zeroLength));
        return sb.append(value).toString();
    }
}

뭔가 조건을 제대로 생각하지 못한 것 같아서 다음에 풀 때는 조금 더 꼼꼼히 생각해 봐야 할 것 같다.