2023 KAKAO BLIND RECRUITMENT - 150367. 표현 가능한 이진트리
[Lv. 3]
https://school.programmers.co.kr/learn/courses/30/lessons/150367
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
우선 예시를 한번 쭉 나열해 보며 감을 잡자.
depth..? height..? 가 1일 때는,
0, 1만이 표현 가능하다.
height = 2이면, 1, 3번째 숫자 중 1이 있다면 2번째 숫자는 무조건 1이여야 하므로, 111, 110, 011, 010, (000)의 4(5)가지의 표현이 가능하다.
height = 3이면, 조건이 여러 가지 붙는데, 우선 1, 3번째 숫자중 1이 있다면 2번째 숫자가 1이여야 하며, 5, 7번째 숫자중 1이 있다면 6번째 숫자가 1이여야 하고, 2, 6번째 숫자중 1이 있다면 4번째 숫자가 1이여야 한다.
또한, 숫자가 들어왔을 때의 height를 계산할 수 있다.
예를 들어 '111'의 경우, 2진수로 변환하면 1101111이므로, 적어도 height=3인 이진 트리로 표현해야 한다.
이를 일반화하면, height = n인 이진트리는, (2n-1)자리의 2진수까지 커버할 수 있고,
이는 즉, 2(2n-1) 인 수까지 height = n인 이진트리로 표현 가능할 수도 있다는 것이다.
다시 문제로 돌아가자면, '63' 이라는 수를 이진트리로 표현할 수 있는 지 없는 지에 대해서 판별하는 것을 하나하나 짚어 보자.
- 일단, '63'을 2진수로 변환하자. '111111'이라는 수로 변환할 수 있다.
- 만약, 자릿수가 2n-1 꼴이 아니라면, 그 꼴이 될 때까지 앞에 '0'을 추가하자. 이 경우에는 '0111111'이 될 것이다.
- root node부터 시작하여, left child, right child를 검사하며, 반복하고, 모든 노드를 검사하자. 우선 '0111111'의 root node는 index=3인 4번째의 '1'이 될 것이다. 여기서부터, 숫자를 빼고 더하면서 height 별로 내려가 보면 된다.
- 총 2n-1꼴에서, n=3인 수이므로, 총 높이는 3이다. root node가 있는 층을 high = 3이라고 한다면, 특정 high인 층에서는, 2(high-2) 만큼 더하고 빼면, right child node와 left child node의 index를 구할 수 있게 된다. 예를 들어, '63' = '0111111'의 경우, root node의 Index=3이고, child node 두개의 index = 1, 5인데, high = 3이므로, root node의 index인 3에서 2만큼 더하고 빼면 1, 5가 나오게 된다.
- 자 이제, BFS와 비슷한 느낌으로, 각 층마다 검사하며, Queue에 검사한 index를 넣어 가며 반복하자. 만약, parent node가 0인데, child node가 1이라면, 그 시점에서 바로 False인 것이다. Queue에 모든 index가 지나가고 나서, Queue에 아무것도 남아있지 않을 때까지 조건에 걸리지 않았다면, 그 때 그 수를 만들 수 있다라고 확인할 수 있게 된다. (True)
그럼, 이런 형식으로 코드를 작성해 보자.
한번에 AC !
from collections import deque
def solution(numbers):
answer = []
for num in numbers:
# num을 binary 2진수로 변환
num = bin(num)[2:]
n = 0
# num의 자릿수가 2^(n-1) ~ (2^n)-1 사이에 있다는 것을 확인
for i in range(10000):
if len(num) < 2**i:
n = i
break
# num의 자릿수가 (2^n)-1자리 꼴이 되도록 앞에 0을 추가
while len(num) != 2**n-1:
num = "0"+num
# root node의 index.
root = len(num)//2
deq = deque([root])
flag = True
while n != 0 and flag:
gap = 2**(n-2)
if n == 1:
break
nextDeq = deque()
while deq:
a = deq.popleft()
left = a - gap
right = a + gap
if num[a] == "0":
if num[left] == "1" or num[right] == "1":
answer.append(0)
flag = False
break
nextDeq.append(left)
nextDeq.append(right)
deq = nextDeq
n -= 1
if flag == True:
answer.append(1)
return answer