[2023 KAKAO BLIND RECRUITMENT] 표현 가능한 이진트리

https://school.programmers.co.kr/learn/courses/30/lessons/150367?language=python3

 

1. 문제 이해

 

입력으로 숫자(1 <= <= 10^15)가 들어오고, 해당 숫자를 표현하는 이진트리가 존재한다면 1, 아니면 0을 출력하는 문제이다.

 

 

이진트리 만드는 과정

1. 입력된 십진수를 이진수로 표현한다. (45 -> 101111)

2. 해당 이진수를 포화 이진트리(perfect binary tree)로 바꾸기 위해서는 해당 이진수의 길이(ex. 101111는 길이가 6)가 2^n - 1 꼴이 되엉 한다. (포화 이진트리의 노드 수는 2^(트리의 높이) - 1 임을 자료구조시간에 배웠을 것이다.)

(101111 -> 0101111 --> 0을 1개 붙여주어야 길이가 7 = 2^3 - 1이 된다.)

3. 얻어진 앞에 0이 붙은 이진수 문자열은 포화이진트리를 LUR 순으로 순회한 결과와 같다. -> 이진트리를 왼, 가운데, 오 순으로 순회

 

 

2. 문제 풀이

"이진트리 만드는 과정" 을 따라가면 앞에 0이 붙은 이진수 문자열을 얻을 수 있다. 해당 문자열로 이진트리가 만들어지는 지 여부는 재귀적으로 생각할 수 있다. 아래의 생각을 따라가보자.

 

 

0101111로 만들어진 트리는 루트 노드의 값(인덱스 3의 값)이 1이므로 해당 가지에서 양쪽에 모두 유효한 이진트리가 붙어있어야 한다.

 

이를 판단하기 위해 해당 트리를 루트를 제외한 두개의 자식 트리로 나눈다. (0101111 -> 010 111)

 

이렇게 하면 자식 트리들 또한 포화 이진 트리이므로 같은 체크 과정을 반복할 수 있다. 즉, 010과 111의 이 모두 유효한 이진트리라면 0101111은 유효한 이진트리이다.

 

루트밖에 없는 트리 (이진수 문자열이 1인 상황)는 유효한 이진트리인것 이 자명하고, 이진수 문자열이 0으로만 구성된 경우에도 유효한 이진트리이다. 더미노드를 추가하는 상황이기 때문이다.

 

즉, 이 두가지 경우를 base step으로 재귀적으로 함수를 구성하며 문제를 해결하였다.

 

조금의 최적화를 위해서 dp역할을 할 dictionary를 정의했고, 이진트리 생성 가능여부가 판별된 이진수 문자열에 대해서의 값을 저장하여, 재귀함수로 들어가는 깊이 수를 O(log(n))번에서 O(1)으로 줄여보았다.

 

그런데, 문제의 인풋 수의 범위가 10^15가 최대이고,  한번의 재귀함수 호출에 대해 최대 50번 정도 들어가게 된다. (10^15 는 약 2^50 이므로)  그리고 인풋 sequence의 길이가 최대 10000이므로 dp dictionary 없이 코드를 돌린다고 가정해도 O(L * log(n)) = O(10000*log(2^50)) = 500000정도라서 효율성 측면에서도 큰 문제가 없을 것 같다. dp dictionay 있이 코드를 돌리면 O(L * 1) = O(10000) = 10000번 정도의 연산이 진행된다. 즉, 수가 아무리 크더라도 영향이 없는 코드를 작성하며 최적화를 진행했다.

 

만약 카카오가 여기서 TLE 코드를 거르기 위해서는 인풋 수를 10^10000정도로 했다면 좋았겠지 ㅋㅋ 근데 코드포스나 백준이 아니고 기업 코딩테스트이어서 이정도의 오바(?)는 하지 않은 것으로 보인다.

 

 

 

3. 코드

from math import pow

## 이진수를 십진수로 바꾸는 함수
def decimal2binary(decimal):
    
    binary = ""
    
    while decimal:
        digit = decimal % 2
        binary += str(digit)
        decimal //= 2
    
    exponent = 0
    zeroCount = 0
    while True:
        
        if int(pow(2,exponent)) <= len(binary) <= int(pow(2,exponent+1)) - 1:
            zeroCount = int(pow(2,exponent+1)) - 1 - len(binary)
            break
        exponent += 1
        
    return "0"*zeroCount + binary[::-1]


def dfs(binary):
    global dp
    
    if binary == "1":
        dp[binary] = 1
        return dp[binary]
    
    ## 0은 가능하다고 
    if set(binary) == {"0"}:
        dp[binary] = 1
        return dp[binary]
    
    ## 이미 있으면 출력하기
    if binary in dp:
        return dp[binary]
    
    length = len(binary)
    
    index = length // 2
    
    ## 중앙이 1인 수
    if binary[index] == "1":
        front = binary[:index]
        back = binary[index+1:]
        
        #print(front, back)
        
        
        if dfs(front) and dfs(back):
            dp[binary] = 1
        else:
            dp[binary] = 0
            
        return dp[binary]
    
    ## 중앙이 0인 쪽은 안된다.
    else:
        dp[binary] = 0
        return dp[binary]
                             
def solution(numbers):
    global dp
    
    dp = {}
    answer = []
    
    
    for number in numbers:
        binaryNum = decimal2binary(number)
        answer.append(dfs(binaryNum))
    
    return answer