[카카오] 표현 가능한 이진트리

문제 이해하기

이진트리를 수로 표현하는 문제입니다. 이진트리의 노드를 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴보고, 더미 노드인 경우 문자열 뒤에 0을 추가하고, 더미 노드가 아닌 경우 문자열 뒤에 1을 추가합니다. 마지막으로 문자열에 저장된 이진수를 십진수로 변환합니다. 

 

문제의 예시인 42를 설명해보자면, 42를 이진수로 변환하면 101010이 됩니다. 이는 완전이진포화트리가 아니기에 0101010으로 변환됩니다.  하위 리프노드에 더미노드가 추가 되야 했지만, 카카오 예시에선 생략되어 있는 모습입니다.

42의 완전포화이진트리

 

문제 해결 방법 설명하기

1. 이진수를 포화 이진트리로 만들 수 있어야 합니다.

 

주어진 정수를 이진수로 변환하여 포화 이진트리를 만드는 것이 요구되고, 이때 0을 삽입해야 합니다.
원본 이진수에 영향을 주지 않으면서 포화 이진트리를 만들 기 위해서 이진수의 앞자리에 0을 삽입한다는 점이 제일 중요합니다.

예를 들면 7을 이진수로 변경한다고 생각해봅시다. 7을 이진수로 변경하면 111이 됩니다. 여기에 000111은 7이지만 111000은 기존의 숫자가 변경됩니다.

따라서 포화 이진트리를 만들 기 위해서 이진수의 앞자리에 0을 삽입해야 합니다

 

2. 이진수가 포화 이진트리인지 판단 할 수 있어야합니다.

 

이진트리의 높이가 존재하면, 포화트리의 노드 개수는 2^(h) - 1이 된다.

그럼 우리의 이진수의 이진트리를 높이를 파악하고자 한다면 log2(n+1) - 1이 된다

따라서 우리는 높이를 구했으니 해당 이진수를 포화이진트리로 변경가능하다.

 

3. 임의로 만든 이진수가 트리의 형식에 위배된는 것이 없는지 검증할 수 있어야 합니다.

예를들면 아래의 그림과 같다 더미 노드의 1 밑에 자식노드인 9가 위치하고 있기 때문에 이 트리는 트리의 정의에 위배된다.

거짓 트리

4. 문자열로 된 포화 트리를 트리로 변환하는 방법

 

우선 문자열의 길이를 2로 나눈 값에 해당하는 노드를 중심으로 왼쪽 서브트리와 오른쪽 서브트리를 만든다. 이때 더미노드가 나오면 해당 서브트리에 있는 모든 노드는 더미노드여야 한다. 그렇지 않으면 3번에서 언급한 위배되는 상황이 발생한다.

코드

def check_head(binary_string, left, right):
    if left == right:
        return 1
    
    mid = (left + right) // 2
    
    if binary_string[mid] == '0':
        for i in range(left, mid):
            if binary_string[i] == '1':
                return 0 
        for i in range(mid + 1, right + 1):
            if binary_string[i] == '1':
                return 0

    
    res1 = check_head(binary_string, left, mid - 1)
    res2 = check_head(binary_string, mid + 1, right)
    
    return res1 & res2


def restort_binary_to_tree(binary_strings):
    import math
    
    digit = 2 ** (int(math.log(len(binary_strings), 2)) + 1) - 1
    binary_strings = "0" * (digit - len(binary_strings)) + binary_strings

    return check_head(binary_strings, 0, len(binary_strings)-1)
        
    

def solution(numbers):
    answer = []

    for number in numbers:
        number = bin(number)
        binary_strings = number.split('b')[1]
        
        answer.append(restort_binary_to_tree(binary_strings))
        
    
    return answer


if __name__ == "__main__":
    print(solution([7, 42, 5]))

 

배운점 정리하기

예시만 보고 이진수의 문자열 길이가 홀수일 때 앞에 0을 추가하여 포화 이진트리로 만들었다고 착각했습니다. 하지만 실제로 입력이 '0000 1 0000'과 같은 구성일 경우 재귀가 종료되지 않는 문제가 발생했습니다.

 

또한 더미노드를 판별하는 과정에서, 리프 노드가 아닌데 더미노드가 나오면 해당 트리는 잘못된 트리라고 판단했었습니다. 그러나 모든 리프 노드가 더미노드일 경우에는 해당 트리 구조가 정상인 것을 까먹고 있었습니다.