문제 설명

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

이진트리를 수로 표현하는 방법은 다음과 같습니다.

이진수를 저장할 빈 문자열을 생성합니다.
주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
문자열에 저장된 이진수를 십진수로 변환합니다.

이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

다음은 이진트리를 수로 표현하는 예시입니다.

주어진 이진트리는 다음과 같습니다.

주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.

노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.

당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.

이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ numbers의 길이 ≤ 10,000
- 1 ≤ numbers의 원소 ≤ 10^15

풀이

2023 카카오 블라인드 채용 코딩 테스트의 4번 문제입니다. 본 문제는 흔치 않은 유형의 문제인데, 재귀, 트리, 수학과 같은 카테고리로 분류할 수 있겠지만 풀이에 있어 가장 중요한 것은 관찰이었습니다. 이진 트리로 표현 가능한 수의 특징을 정확히 캐치할 수 있다면 큰 구현력을 요구하지 않고도 풀 수 있는 문제입니다.

이진 트리로 표현 가능한 수의 특징 중 하나는 트리의 특징을 통해서 알아낼 수 있습니다. 트리는 루트 노드와 자식 노드로 이루어진 여러 서브 트리들의 집합체로, 루트 노드가 없다면 트리는 존재할 수 없습니다. 이 사실을 통해 이진수로 변환한 수에서 루트 노드에 위치한 수가 0이라면 이진 트리로 표현할 수 없음을 알 수 있습니다.

하지만 루트 노드가 0인 상황에서 한 가지 예외가 있는데, 바로 트리를 이루는 모든 수가 0일 경우입니다. 이 경우에는 해당 서브 트리가 아예 존재하지 않는다는 것으로, 이진 트리로 표현 가능 여부에는 영향을 미치지 않습니다. 따라서 이진 트리로 표현 가능한 수의 특징은 다음과 같이 정의할 수 있습니다.

루트 노드에 위치한 수가 1이어야 한다.
다만, 서브 트리를 이루는 모든 수가 0인 경우는 예외이다.

위 두 조건을 통해서 트리를 구성하는 수의 갯수가 1개, 즉 루트 노드만 있을 때에는 숫자에 관계없이 항상 참임을 추가로 알 수 있습니다.

그런데 여기까지 도출을 했음에도 아직 문제를 풀 수 없습니다. 바로 이진수를 이진 트리로 표현 가능한지 검사 가능한 형태로 변환해야 하기 때문입니다.

문제에서 이진수는 보이는 노드와 보이지 않는 노드로 인해 결국 포화 이진 트리로 표현되는데, 포화 이진 트리의 특징 중 하나는 바로 노드의 갯수가 2^n - 1개라는 것입니다. 따라서 이진수로 변환한 수의 길이가 이를 만족하지 않는다면 이진 트리로 표현할 수 없습니다. 따라서 이진수의 길이를 2^n - 1개의 형태로 맞춰주되, 숫자에는 변화가 없도록 앞에 0을 붙여줘야 합니다.

따라서 최종적으로 본 문제는 다음과 같은 과정을 통해 해결할 수 있습니다.

이진수 변환
이진수를 검사 가능한 형태로 변환
이진 트리로 표현 가능한지 판단

부가적으로 Kotlin의 경우 toString(n) 메서드를 통해 진수 변환을 간단히 할 수 있습니다.

전체 코드

class Solution {
    
    tailrec fun isOk(bin: String): Boolean {
        if(bin.length == 1) return true

        val mid = bin.length / 2
        val left = bin.take(mid)
        val right = bin.takeLast(mid)

        if(bin[mid] == '0') {
            if(bin.any { it == '1' }) return false
            return true
        }

        return isOk(left) && isOk(right)
    }
        
    fun solution(numbers: LongArray): IntArray {
        val answer = mutableListOf<Int>()

        for(num in numbers) {
            val bin = num.toString(2).let {
                var n = 0.0
                while(Math.pow(2.0, n).toInt() - 1 < it.length) n += 1
                "0".repeat(Math.pow(2.0, n).toInt() - 1 - it.length) + it
            }

            if(isOk(bin)) answer.add(1)
            else answer.add(0)
        }

        return answer.toIntArray()
    }
}

Android Developer

[2023 카카오 블라인드] 표현 가능한 이진트리 풀이 (프로그래머스)

문제 설명

제한사항

풀이

전체 코드