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

문제

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

프로그래머스

 

문제 풀이

문제를 읽어도 전혀 이해가 가지 않았다. 주어진 이진트리가 뭐지? 무슨 규칙이 있는 건가? 싶어서

무작정 문제에 대한 예시를 그려보았다.

 

우선 문제에 대한 예시로 나온 숫자들을 2진수로 바꾸면 다음과 같다.

그리고 문제에서 포화 이진트리로 생성해야 했기에, 0을 채워줬다.

포화 이진트리는 깊이가 n일때 노드의 개수는 2ⁿ -1으로 맞춰줘야 한다.

따라서 42와 63 모두 깊이가 3이지만 노드의 개수가 6개였기에, 7개로 맞춰주기 위해서 0을 채워줬다.

보면 5와 95는 이진트리로 만들기 불가능하다고 예시에서 주어졌다.

 

문제에서 숫자는 왼쪽에서부터 채워진다고 했기 때문에 다음과 같은 트리로 만들 수 있다.

해당 숫자들을 이진트리로 표현하지 못하는 이유는 부모가 0이기 때문이라고 생각했다.

즉 부모가 0이면 이진트리로 표현하지 못한다!라는 사실을 예시를 통해서 얻을 수 있다.

 

하지만 문제를 풀다가 틀려서 다른 분의 풀이를 보니 부모가 0이라도 자식들이 모두 0이라면 이진트리로 표현이 가능하다는 것이었다.

아무리 봐도 예를 통해서 추출할 수 없는 사실인데.. 좀 궁금하다.

 

아무튼 그럼 우리는 이진트리로 만들지 못하는 경우에 대해서 정리할 수 있다.

1. 부모가 0인데 자식이 1이 포함되어 있는 경우

해당 경우만 제외하면 모두 이진트리로 표현이 가능하다.

 

이러한 배경지식을 가지고 이제 문제를 풀면 된다.

 

우선 입력받은 숫자를 2진수로 바꿔줘야 한다.

해당 과정은 2로 계속 나누면서 나머지를 채워주면 될 것이다.

여기서 주의할 점은 해당 과정에서 2진수 배열이 거꾸로 형성되기 때문에, 뒤집어주거나 나중에 작업할 때 계속 뒤집어서 해줘야 한다.

나는 여기서 reversed()를 사용해서 처음부터 뒤집은 2진수 문자열을 반환했다.

그런 다음 포화트리로 만들어줬다.

이진수 문자열의 길이에 따라서 층을 정할 수 있기 때문에 포화트리로 만들어줬다.

당연하게도 남는 자리는 0을 채워야 한다.

앞에서부터 채워줘야 하기에 StringBuilder()를 사용했다.

 

다음은 이제 이진수 문자열을 트리형태로 쪼개주는 작업이다.

해당 작업은 분할정복으로 해도 되고, 실제 트리를 만들어서 탐색을 진행해도 되지만, 분할정복으로 하는 것이 한 번에 할 수 있기 때문에 그렇게 진행했다.

방법은 간단하다.

1. 문자열을 가운데로 쪼갠다.
2. 여기서 가운데는 root가 되고, 0부터 root-1까지가 왼쪽 서브트리이고, root+1부터 끝까지 오른쪽 서브트리를 형성할 것이다.
3. 그렇다면 왼쪽 서브트리를 다시 재귀함수로 호출하고, 오른쪽 서브트리를 다시 재귀 함수로 호출해서 검사를 진행한다.
4. 재귀함수가 true를 반환하는 조건은 아래와 같다.
   • 길이가 1일 경우
   • 1을 포함하지 않는 경우 -> 위에서 설명한 부모가 0이고, 자식이 0인 경우
   • 루트가 1이고, 왼쪽 서브트리, 오른쪽 서브트리의 결과가 true일 경우
5. 트리를 만들 수 있다면 1이고, 아니라면 0을 넣어준다.

 

전체 코드

import java.io.*
import java.lang.*

class Solution {
    fun solution(numbers: LongArray): IntArray {
        var answer = IntArray(numbers.size) { 0 }
        for (i in 0 until numbers.size) {
            var str = makeBinaryNumber(numbers[i]) // 이진수로 표현
            str = makeFullTree(str) //포화트리로 표현
            if (str.length == 1 && str == "0") {
                answer[i] = 0
                continue
            }
            if (isEnabledFullBinaryTree(str)) { //이진 트리 가능
                answer[i] = 1
            } else { //이진트리 불가능
                answer[i] = 0
            }
        }
        return answer
    }

    fun makeBinaryNumber(number: Long): String { //Long을 이진수로 표현함
        var result = StringBuilder()
        var num = number
        if (num == 0L) return "0"
        while (num > 0) { //이진수로 만들기
            result.append(num % 2) //나머지를 계속 박기
            num /= 2
        }
        return result.toString().reversed() //뒤집어주기
    }

    fun makeFullTree(number: String): String { //노드의 개수는 2^n - 1 개. 꽉곽 채워준다.
        var zero = StringBuilder()
        var n = 2
        while (true) {
            if (number.length <= n - 1) break
            n *= 2
        }
        for (i in 0 until n - 1 - number.length) { // 포화 이진트리로 만들어주기.
            zero.append("0")
        }
        return zero.append(number).toString()
    }

    fun isEnabledFullBinaryTree(number: String): Boolean {
        if (number.length == 1 || !number.contains("1")) return true //길이가 1이거나, 1을 포함하지 않는 경우는 트리 형성 가능
        val root = number.length / 2  //문자열의 중간
        val left = number.substring(0, root) //왼쪽 0~root-1까지
        val right = number.substring(root + 1, number.length) //root+1부터 끝까지
        if (number[root] == '1' && isEnabledFullBinaryTree(left) && isEnabledFullBinaryTree(right))
            return true
        return false
    }
}