[프로그래머스 Lv3] 파이썬 - 표현 가능한 이진 트리

프로그래머스 - 표현 가능한 이진트리

# 조건

• 당신은 이진트리를 수로 표현하는 것을 좋아합니다.
• 이진트리를 수로 표현하는 방법은 다음과 같습니다.
  1. 이진수를 저장할 빈 문자열을 생성합니다.
  2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
  3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
  4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
  5. 문자열에 저장된 이진수를 십진수로 변환합니다.
• 이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.
• 다음은 이진트리를 수로 표현하는 예시입니다.
• 주어진 이진트리는 다음과 같습니다.

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

• 노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다.
• 이 이진수를 십진수로 변환하면 58입니다.
• 당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.
• 이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다.
• numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

# 접근 방법

• 트리에 대해서 잘 알고 있어야 풀 수 있는 문제이다.
• 우선 이진 트리에서 leaf node는 자식이 없는 노드를 의미하고, root node는 트리의 시작노드, subtree는 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리이다.
• 문제 설명의 "이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다." 는
  • 트리 순회 방식 중 중위 순회(inorder traversal)을 의미한다.
  • 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드의 순으로 이진수가 생성되는 것이다.
• 주어진 자연수를 이진 수로 변경 한 뒤 이진 포화 트리로 만들어 줄 수 있는지 체크를 하는 문제이다.
  • 포화 이진 트리는 2^n -1 개의 노드를 가진다.
  • 부족한 자릿수는 왼쪽에 0을 추가해주면 된다.
• 이렇게 만들어 준 이진수는 중위 순회로 나열 되기 때문에 전체 길이의 중간이 부모 노드, 그 양 옆의 중간이 subtree의 부모 노드가 되는 점을 참고하여 체크해준다.
  • 리프 노드가 아닌 루트 노드가 0인 경우 더미 노드가 되므로 이진 포화 트리로 만들 수 없다.
  • 이 때, // 2 씩하며 리프 노드를 들어가주며 부모 노드의 여부를 체크해준다.
• 부모 노드가 0이라면 False를 리턴해주기 때문에 길이가 1이라면 => 리프 노드라면 무조건 True를 리턴해주면 된다.
  • 이 때, 0 0 0과 같은 경우가 존재 할 수 있으므로 조건에 not '1' in b_num을 추가하여 서브 트리 자체가 없을 수도 있는 것을 체크해주어야 한다.

from math import log
def solution(numbers):
    answer = []
    # 이진 포화 트리, 중위 순회를 이용한 문제
    # 전체 노드 수 -> 2^(h+1) -1 이 되어야 하므로
    # 2진수로 변경 후 부족한 자리수는 왼쪽에 0을 추가해준다.
    for i in numbers:
        b_num = bin(i)[2:]
        # 2진수의 길이를 로그로 나눠주면 높이가 나온다.
        need = 2 ** (int(log(len(b_num), 2)) + 1) - 1
        # 부족한 만큼 0 추가
        b_num = '0' * (need - len(b_num)) + b_num


        # 루트 노드가 0인지 체크해주기
        # 또한 서브 트리 자체가 없을 수 있으므로 모두 0 0 0 과 같은 경우를 체크해주기
        def check(b_num):
            if len(b_num) == 1 or not '1' in b_num:
                return True

            mid = len(b_num) // 2
            if b_num[mid] == '0':
                return False

            return check(b_num[:mid]) and check(b_num[mid+1:])

        answer.append(check(b_num))
        for i, j in enumerate(answer):
            if j:
                answer[i] = 1
            else:
                answer[i] = 0
    return answer