문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150367
문제 파악
이진 트리를 수로 표현한다고 한다.
이렇게 생긴 이진트리가 있다.
리프노드가 없는 노드에 더미 노드를 점선으로 추가했다.
그리고 왼쪽 아래,중간,오른쪽 아래노드 순으로(중위순회) 순회하며 번호를 붙였다.
그 후 더미 노드는 '0', 더미노드가 아닌 실제 노드에는 '1'을 붙여 문자열로 나타내면
'0111010'이 되고 이를 십진수 로 변환하면 58이 된다.
이 방법이 이진 트리를 십진수로 표현하는 방법이라고 할때,
문제에서는 배열에 여러 정수를 담아 입력받는다.
이때 이 입력받은 정수들이 이렇게 이진 트리로 표현 가능한지 아닌지가 궁금하다고 한다.
가능하면 1을, 없다면 0을 배열에 담아 return 하라고 한다.
<제한 사항>
입출력 예시에서 7,42,5 를 보면
7은 아래 그림과 같이 표현할 수 있다.
111(2) = 1+2+4 = 7
42는 어떻게 표현할 수 있을까?
우선 2진수로 나타내면
42는 2의 5승 더하기 2의 3승 더하기 2의 1승이니
101010(2) 이다.
이진 트리의 노드의 개수는 2의 n승-1 이어야 한다.
그렇기 때문에 101010은 6이라 이진 트리가 될 수 없다.
그러나 맨 앞에 0을 붙여준다면 가능하다 0101010(2)
2의 3승-1 = 7
그러면 다음 그림으로 나타내진다.
마지막 5의 경우는 어떨까?
5는 이진수로 표현했을 때 101 이다.
2의 n승-1 으로 표현이 가능하지만
루트 노드가 0이 되어 이진트리로 표현할 수 없다.
95의 경우에는 어떨까?
- 95를 이진수로 나타내면
-> 64+16+8+4+2+1 = 1011111(2) 이다.
길이는 7이니 가능하므로 그대로 이진트리로 그려보면
이렇게 리프노드가 아닌 노드가 비어있으면 문제에서 이진트리라고 보지 않는다.
즉 문제에서는
- 입력받은 정수를 2진수로 표현한다.
- 2^n-1 (1,3,7,15,31...) 꼴로 더미노드를 추가한다.
- 부모노드가 더미노드(0) 일때 자식노드가 더미노드가 아니라면(1) 이진트리로 해당 수를 표현할 수 없다.
해답 및 풀이
# 이진수 만들기 함수
# 이진수 만들기 함수
def to_binary(n):
if n == 0 :
return "0"
bits = []
while n > 0:
bits.append(str(n % 2))
n //= 2
bits = ''.join(reversed(bits))
return bits
# 2^n-1 꼴이 되게 앞에 더미(0) 붙여주기
def add_dummy_node(bits):
L = len(bits)
full = 1
while full < L:
full = full * 2 + 1
need = full - L
return '0' * need + bits
def dfs(bits,idx,depth): # bits: 배열, idx: 부모 인덱스, depth: 자식까지의 거리
# 리프 노드까지 내려왔다면 이진트리임
if depth == 0 :
return True
# 부모가 '0'인데 자식이 '1'이면 이진트리가 아님
if bits[idx] == '0':
left_child = idx - depth
right_child = idx + depth
if bits[left_child] =='1' or bits[right_child] == '1':
return False
# 왼쪽, 오른쪽 서브트리 탐색
left = dfs(bits,idx - depth, depth // 2) # depth를 2로 나누는 이유는 depth 는 트리의 깊이가 아니라 부모노드에서 자식노드의 인덱스 까지의 거리이기 떄문이다. 자식노드의 루트 노드는 바로옆이 아니라 부모노드에서 depth//2 만큼 떨어진 곳에 있다.
right = dfs(bits,idx + depth, depth // 2)
return left and right
def solution(numbers):
answer = []
for n in numbers:
# 1. 2진수 변환
bits = to_binary(n)
# 2. 더미 추가
bits = add_dummy_node(bits)
# 3. 루트 인덱스와 depth 계산
root_idx = len(bits) // 2 # 루트 노드의 인덱스는 중앙에 있다. ex) 111 이라면, 루트노드의 인덱스는 len(111)=3 //2 = '1'
depth = (len(bits) + 1) // 4 # 트리의 깊이 ex) len(bits)=7 이라면 +1 해주고 4로 나누어 준것이 깊이이다. 15라면 깊이는 4
# 4. DFS
valid = dfs(bits,root_idx,depth)
answer.append(1 if valid else 0)
return answer이진수로 변환하는 함수와 더미 노드를 추가하는 함수는 구현하였지만
dfs 구현에서 어려움을 겪었다.
루트 노드의 인덱스 찾기와
부모노드에서 자식노드로의 거리를 구하는 방식이 익숙치 않았다.
배열에서 부모 노드(인덱스) 에서 자식 노드(인덱스) 찾기는 배열로 접근하기보다 트리(그림) 인덱스를 다 적어놓고 배열과 비교하며 어떤식으로 찾으면 좋을지 접근하는 것이 좋아보인다.
