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

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

프로그래머스

 

1. 문제 이해

십진수 58 (이진수 "0111010")을 표현한 이진 트리

문제에서 주어진 트리는 포화 이진 트리(Perfect Binary Tree)이며 노드 탐색 순서를 보면, left-root-right로 Inorder Traversal(중위 순회)이라는 것을 알 수 있다.

노드는 더미노드일 경우 이진 트리 노드 그림에서 점선으로, 문자열에서는 0으로 표시된다. 더미 노드가 아닐 경우 실선, 1로 표시된다.

 

1. 구하고자 하는 것

: 십진수가 주어졌을 때, 하나의 이진트리로 해당 수를 표현할 수 있는지의 여부

 

2. 입력값

: numbers [int 배열]

=> 이진트리로 만들고 싶은 십진수를 담은 1차원 정수 배열

 

3. 출력값

: result [int 배열]

=> 해당 십진수를 이진트리로 표현할 수 있다면 1, 없다면 0을 1차원 정수 배열에 담아 return

 

4. 제한 사항

1 <= numbers의 길이 <= 10,000

1 <= numbers의 원소 <= 10^15

 

5. 예시 

해당 예시는 58의 십진수(이진수 "0111010")를 이진트리로 만들 수 있으므로 1을 result 배열에 담아서 출력해야 한다.

2. 설계

1. 십진수 -> 이진수 변환하기

2. 이진수를 포화이진트리(Perfect Binary Tree) 형식으로 구성하기. 

 -> 이진수를 포화 이진 트리로 만들기 위해 필요한 노드 갯수(2^n-1)를 구한 뒤, 이진수 문자열의 길이에서 부족한 만큼 앞에서 0을 패딩해준다. 

3. 패딩한 이진수로 이진 트리 구현이 가능한지 검증한다.

-> root노드를 포함한 부모 노드는 무조건 1이어야 한다. (비워져 있으면 안됨) 

  3-1) root 노드(부모 노드)가 1일 경우, 이어서 자식 노드(왼쪽 서브트리, 오른쪽 서브트리)도 재귀로 확인

  3-2) 0일 경우 자식 노드들 값 확인

    : 자식 노드들 중 1이 하나라도 존재할 경우, 이진 트리가 될 수 없다!

 

3. 풀이

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

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

        for (int i = 0; i < numbers.length; i++) {
            // 1. 십진수 -> 이진수 변환
            long number = numbers[i];
            String binaryString = Long.toBinaryString(number);

            // 2. Perfect Binary Tree로 맞춰주기. (0 패딩)
            int length = binaryString.length(); // 이진수로 변환된 문자열 길이 (패딩 전)
            int depthCnt = 1; // 마지막 노드(리프노드)의 depth에서 필요한 노드 갯수
            int cnt = 1; // 이진트리 노드 갯수

            while (length > cnt) {
                depthCnt *= 2;
                cnt += depthCnt;
            }

            binaryString = "0".repeat(cnt - length) + binaryString;
            
            // 3. 이진 트리 검증 -> 정답 배열에 저장
            answer[i] = isValid(binaryString.toCharArray(), binaryString.length() / 2, 0, binaryString.length()-1, false) ? 1: 0;
        }
        return answer;
    }

	// 이진 트리 검증 메서드
    private boolean isValid(char[] arr, int rootIdx, int l, int r, boolean shouldBeZero) {
        // 부모가 0인데 자식 노드가 0이 아닐 경우 이진 트리 불가능
        if (shouldBeZero && arr[rootIdx] != '0') return false;
        // 리프노드일 경우, 이진 트리 가능 (앞 조건을 통과해서 이진트리 가능한데 리프노드까지 탐색한 경우)
        if (l >= r) return true;

        int leftMid = (l + rootIdx) / 2;
        int rightMid = (rootIdx+1 + r) / 2;
        boolean isZero = arr[rootIdx] == '0';
        
        return isValid(arr, leftMid, l, rootIdx-1, isZero) && isValid(arr, rightMid, rootIdx+1, r, isZero);
    }

}

4. 느낀점

문제 설명이 불친절하나 트리 이해 문제로 아주 좋은 문제라고 생각한다.

이진 트리 검증 뿐만 아니라, 포화 이진트리와 십진수->이진수 변환 등을 더한 응용 문제라서 트리를 잘 이해하고 있는지와 이해한 내용을 바탕으로 문제 조건을 세부적으로 설계할 수 있는지 등을 볼 수 있다.

 

예전에 공부했던 유튜브 [대한민국 엔지니어] 트리 문제 아이디어가 문제 접근을 하는데 많은 도움이 되었다. (뿌듯^_^) 

 

그런데 "포화 이진 트리"가 무엇인지.. 명확히 생각나지 않았다. 

정확히 말하자면 우리나라에서 "포화 이진 트리"로 번역된 것에 문제가 있는 경우가 있다고 들어서 명칭을 영어로 알고 있어서 헷갈렸다.(밑의 tree 영상 참고)

우리나라에서는 perfect binary tree를 포화 이진 트리라고 번역해놓고 설명은 full binary tree로 해놓은 교재가 있다고 해서 한국 번역이 아닌 영어로 정리해두고 있었는데 문제에 포화 이진트리라고 적혀 있어서 당황했던 것.

 

그래도 문제 그림과 설명에서 빈 노드들을 다 0으로 채워놓은 것을 보아 포화 이진트리를 Perfect Binary Tree로서 사용했다는 것을 유추 가능했다.

 

+ 개인적으로 재귀랑 이분탐색.. 아직 익숙지 않고 자잘한 실수가 나오는데 많이 연습해야겠다.. 

재귀 종료 조건에서 처음에 l==r로 했었는데 r이 l 밑으로 넘어가는 경우가 있더라... l<=r을 찍어보면서 찾았다ㅜ 

mid 구하는 것도 실수 1/2로 제대로 분리 못하는바람에 stackoverflow 났었음..

 

 

5. 풀이에 도움이 되었던 자료

1. 트리 종류

https://www.youtube.com/watch?v=LnxEBW29DOw&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP&index=1 

 

2. 트리 순회 방법

https://www.youtube.com/watch?v=QN1rZYX6QaA&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP&index=2 

 

3. 배열을 이진검색트리로 만들기

* 문제에서는 이진검색트리가 아니라 이진트리지만, inorder 방식으로 순회하며 문자열이 정렬되어 있기 때문에 아이디어 사용 가능

https://www.youtube.com/watch?v=9ZZbA2iPjtM&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP&index=8