https://school.programmers.co.kr/learn/courses/30/lessons/150367
이진트리를 완전이진트리로 만들 때, 추가해야하면 0을 아니라면 1을 주고, 중위순회를 하면서 해당 노드에 적힌 숫자를 이어붙일 때 나오는 이진수를 십진수로 변환해야한다.
그리고 문제는 십진수 주고 위의 과정을 통해서 만들어낼 수 있는 수인지 확인하라고 하는 문제이다.
Python
import sys
sys.setrecursionlimit(10 ** 6)
def solution(numbers):
answer = []
for n in numbers:
b = list(map(int, list(str(bin(n))[2:])))
if maketree(b):
answer.append(1)
else:
answer.append(0)
return answer
def maketree(n):
l = 0
while 2**(l+1)-1 < len(n):
l += 1
tree = [0] * (2 ** (l + 1) - 1 - len(n)) + n
return dfs(tree, len(tree)//2)
def dfs(tree, now):
if sum(tree) == 0:
return True
elif tree[now] == 0:
return False
elif len(tree) == 3:
return True
ltree = tree[:now]
rtree = tree[now+1:]
return dfs(ltree, len(ltree)//2) and dfs(rtree, len(rtree)//2)
문제를 이해하는데 한참 걸렸고, 5가 왜 안 되는지 이해하는데도 한참이 걸렸다.
기본적으로 이런 모습이라서 안 되는 것인데 자꾸만
저런 모습이면 탐색할 때 101이 나와서 가능하지 않은가 하는 의문이 들었다.
그러나 문제의 조건은 포화이진트리를 만드는 것이기에 저런 불완전한 모습이 아닌
이런 모습이 나와야 하고 그러면 오른쪽에 추가되는 노드로 인해 이진수는 101000, 1010이 나오게 된다.
그래서 어떻게 하던 101은 나올 수 없다는 것을 이해 못하다가 도형으로 확인해보니까 이해할 수 있게 됐다.
그래서 입력받은 정수를 2진수로 변환하고, 2진수의 길이를 감당할 수 있는 최소길의의 이진트리를 만들었다.
n층을 가진 완전이진트리의 노드 개수는 2^(n)-1이기에 해당 길이에 현재 이진수 길이를 뺀 것만큼 0을 왼쪽에 추가해주고 그 뒤에 이진수를 붙였다.
그리고 dfs 함수를 통해서 왼쪽, 오른쪽 자식트리를 탐색하게 했는데 만약 트리의 합이 0이라면 트리가 루트부터 통으로 추가된 노드로 구성되어서 True를 반환했다.
또한, 만약 트리 합이 0이 아닌데 루트가 0이면 존재할 수 없는 트리라서 False를 반환해주었고, 마지막으로 트리의 노드 수가 3이고 루트가 1이라면 자식까지 안 가봐도 돼서 바로 True를 반환했다.
그렇지 않은 나머지 트리에 대해서는 가운데를 기준으로 리스트 2개로 쪼개고 각각에 대해서 dfs를 진행했다.
머리로 이해가 안 가면 그림을 그려보자.
