2023 Kakao Blind - 표현 가능한 이진트리
Level: 3
Language: Java
Comment: dfs
URL: https://programmers.co.kr/learn/courses/30/lessons/150367
전체 코드: https://github.com/juhwanHeo/algorithm/blob/main/src/main/java/com/programmers/kakao2023/blind/Test4.java
테스트 코드: https://github.com/juhwanHeo/algorithm/blob/main/src/test/java/com/programmers/kakao2023/blind/Test4Test.java

0. 문제 설명

• 문제 URL 참고

1. 로직

I. Long.toBinaryString으로 2진수 변환

StringBuilder binary = new StringBuilder(Long.toBinaryString(numbers[i]));

II. 포화 이진트리 만들기

• 2진수로 변환한 binary의 길이로 Tree Level을 찾는다.

int len = binary.length(), level = 0;

// Tree Level 찾기
while (len != 0) {
    len >>= 1;
    level++;
}

• ex) binary의 길(len)이: 6
  • 110(6) -> 11(3) -> 1(1) -> 0(0)
  • level: 3
• 구한 Level로 포화이진트리 만들기
  • 2 ^ level - 1 만큼 문자열 앞에 0으로 채워 포화 이진트리 생성

// 포화 이진트리 만들기
while (binary.length() != Math.pow(2, level) - 1) {
	binary.insert(0, "0");
}

III. L --> D --> R (중위 순회)

• 문제에 설명되어 있듯 왼쪽에서부터 오른쪽까지 탐색 시작
• Binary Search 처럼 (start + end) / 2 로 왼쪽 오른쪽 구분
• Binary Search 처럼 visited의 0번째는 사용하지 않는다.
  • 인덱스로 접근하기 편리하려고
  • mid == 0 이면 dfs 종료조건에 추가
• 이전 값이 0 이고, 현재 값이 1 인 경우 이진트리로 표현이 불가능함.
  • 포화 이진트리로 만들고 부모가 더미노드인데 자식이 더미노드가 아니면 규칙에 위배됨
  • 4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.

static void dfs(int start, int end, char before, String binary) {
    int mid = (start + end) / 2;
    if (visited[mid] || mid == 0) return;
    char current = binary.charAt(mid - 1);

    // L
    dfs(start, mid - 1, current, binary);

    // D
    visited[mid] = true;
    if (before == '0' && current == '1') {
        isOk = false;
        return;
    }

    // R
    dfs(mid + 1, end, current, binary);
}

2. 전체 코드

/*
 * @2023 KAKAO BLIND RECRUITMENT
 * @TestName: 표현 가능한 이진트리
 * @URL: https://programmers.co.kr/learn/courses/30/lessons/150367
 * @COMMENT: binary Search 하듯이 dfs 진행
 */
public class Test4 {

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

        for (int i = 0; i < numbers.length; i++) {
            StringBuilder binary = new StringBuilder(Long.toBinaryString(numbers[i]));
            int len = binary.length(), level = 0;

            // Tree level 찾기
            while (len != 0) {
                len >>= 1;
                level++;
            }

            // 포화 이진트리 만들기
            while (binary.length() != Math.pow(2, level) - 1) {
                binary.insert(0, "0");
            }

            isOk = true;
            visited = new boolean[binary.length() + 1];
            dfs(1, binary.length(), '1', binary.toString());

            answer[i] = isOk ? 1 : 0;
        }

        return answer;
    }

    /* L --> D --> R */
    static void dfs(int start, int end, char before, String binary) {
        int mid = (start + end) / 2;
        if (visited[mid] || mid == 0) return;
        char current = binary.charAt(mid - 1);

        // L
        dfs(start, mid - 1, current, binary);

        // D
        visited[mid] = true;
        if (before == '0' && current == '1') {
            isOk = false;
            return;
        }

        // R
        dfs(mid + 1, end, current, binary);
    }
}

후기

dfs로 Binary Search(이분탐색) 하는 것이 매우 흥미로웠던 문제였다.