표현 가능한 이진트리(카카오) 문제풀이

문제 

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

프로그래머스

 

문제 접근 방식

수가 주어졌을 때 해당 수를 이진수로 변환하고, 해당 이진수에서 1에 해당하는 숫자들을 포화 이진트리에 넣어서 해당 트리가 가능한 트리인지를 확인하는 문제이다. 문제의 핵심적인 부분은 아래와 같다.

1. 이진수를 포화이진트리에 어떻게 넣을 것인가?
2. 전제 노드 개수를 어떻게 구할 것인가?
3. 해당 이진트리가 표현될 수 있는 조건은 무엇인가?

 

 

1. 이진수를 포화 이진트리에 어떻게 넣을 것인가?

기존 십진수를 이진수로 변환하는 것은 파이썬 라이브러리를 사용해서 간단하게 할 수 있다. 이진수의 1에 해당하는 것에는 노드가 존재하고, 0 에 해당하는 것들은 노드가 존재하지 않으면 되는데 어떻게 넣을 수 있을까?

 

예를 들어 확인해보자. 

15의 이진수인 1111 은 이진트리로 나타내면 어떻게 될까? 아래 사진과 같이 오른쪽과 루트에는 실선노드가 존재하고 왼쪽 부분은 더미노드로 채워질 것이다. 점선 노드를 0으로 표현해보자면, 1111은 0001111 으로 표현할 수 있다. 이진수의 자릿수 4개를 통해 전체 노드 개수가 정해지는 것을 알 수 있다. 전체 노드의 개수를 구하고 오른쪽 부터 이진수를 채운 후 나머지를 0으로 채우면 이진 트리를 배열로 표현할 수 있다.

 

 

이진수를 트리에 어떻게 넣을지 정리를 해보자면 아래와 같다.

1. 이진수의 크기를 통해 포화 이진트리의 노드 개수를 구한다.
2. 노드 개수의 크기의 배열을 선언하고, 이진수를 오른쪽부터 채운다.

 

 

2. 전체 노드 개수를 어떻게 구할 것인가?

위에서 이진수의 크기를 통해 포화 이진트리의 전체 노드 개수를 구한다고 했는데 어떻게 구할 수 있는지 구체적으로 알아보자. 트리의 높이 k가 1씩 증가할 때 마다 리프 노드의 개수가 2^(k-1) 개씩 증가한다. 즉, k 까지의 전체 노드 개수는 2^0 + 2^1 + ... 2^(k-1) 이며, 이를 정리하면 2^k -1 이 된다.

따라서, k를 1 씩 증가시키면서 전체 노드 개수를 늘려나가고, 아래 조건을 만족하면 이진 트리의 전체 노드 개수를 구할 수 있다.

2^(k-1)-1 < (이진수 길이) <= 2^k-1 
위의 식을 만족하는 k에 대해, 
완전 이진 트리 전체 개수 = 2^k-1

 

def get_tree_size(binary):
    size = len(binary)
    i = 1
    while True:
        tree_size = 2 ** i - 1
        if tree_size >= size:
            return tree_size
        i += 1
    return 1

 

 

 

3. 해당 이진트리가 표현될 수 있는 조건은 무엇인가?

표현될 수 있는 조건을 생각하기가 어려워서 표현될 수 없는 경우를 생각해보았다. 아래 사진과 같이 부모 노드는 존재하지 않는데 자식 노드가 존재하는 경우는 모순이기 때문에 트리를 표현할 수 없다. 따라서, 전체 트리에 대해서 재귀함수를 사용하여 부모노드는 존재하지 않는데 자식 노드가 존재하면 False를 반환하도록 하고, 그 이외의 경우는 True를 반환한다. 이렇게 하여 이진 트리가 표현될 수 있는지 판별한다.

 

def is_possible(tree, start, end):
    if start == end:
        return True
    mid = (start + end) // 2 # 부모노드

    left_mid = (start + mid - 1) // 2 # 자식노드 left
    right_mid = (mid + 1 + end) // 2 # 자식노드 right

    # 부모노드는 없는데 자식 노드가 존재한다면 False 반환
    if tree[mid] == '0' and (tree[left_mid] == '1' or tree[right_mid] == '1'):
        return False

    # 후손 노드에서 가능하지 않다고 판단이 나온다면 Fasle 반환
    if not is_possible(tree, start, mid - 1) or not is_possible(tree, mid + 1, end):
        return False

    # 그렇지 않다면 True 반환
    return True

 

 

시간 복잡도

numbers의 길이가 최대 1e4이고 선형 탐색을 해야한다. 그리고 내부에서 이진수 길이에 해당하는 만큼 순회를 해야한다. 이진수의 자릿수의 경우 log2(10^15) 이며, 10^15 = 약 2^50 이기 때문에 최대 50 자리를 가지게 된다. 이진수를 탐색하는데 걸리는 시간은 상수시간에 해당하므로 전체 시간복잡도는 O(N)이 걸린다.

 

코드

# 기능 : 트리의 [start,end] 구간에서 트리가 성립하는지를 확인한다
# 입력 : 트리 및 구간
# 출력 : 해당 구간에서 트리 표현 여부
def is_possible(tree, start, end):
    if start == end:
        return True
    mid = (start + end) // 2 # 부모노드

    left_mid = (start + mid - 1) // 2 # 자식노드 left
    right_mid = (mid + 1 + end) // 2 # 자식노드 right

    # 부모노드는 없는데 자식 노드가 존재한다면 False 반환
    if tree[mid] == '0' and (tree[left_mid] == '1' or tree[right_mid] == '1'):
        return False

    # 후손 노드에서 가능하지 않다고 판단이 나온다면 Fasle 반환
    if not is_possible(tree, start, mid - 1) or not is_possible(tree, mid + 1, end):
        return False

    # 그렇지 않다면 True 반환
    return True


# 기능 : 이진수를 통해 완전 이진트리의 노드개수를 구한다
# 입력 : 이진수
# 출력 : 완전 트리의 노드 개수
def get_tree_size(binary):
    size = len(binary)
    i = 1
    while True:
        tree_size = 2 ** i - 1
        if tree_size >= size:
            return tree_size
        i += 1
    return 1


def solution(numbers):
    answer = []

    for number in numbers:
        binary = format(number, 'b')

        n = get_tree_size(binary) # 트리의 노드 개수를 구한다
        tree = ['0'] * n

        for i in range(len(binary)): #완전 이진트리의 오른쪽 끝부분부터 이진수의 오른쪽 수를 채워넣는다.
            tree[n - i - 1] = binary[-i - 1]

        if is_possible(tree, 0, n - 1): # 해당 이진수로 표현 가능한지를 판단한다.
            answer.append(1)
        else:
            answer.append(0)
            
    return answer

 

 

회고

1. 이진트리를 배열을 통해 관리하는 방법
2. 트리가 성립하지 못하는 조건
3. 십진수를 이진수로 변환하는 파이썬 함수