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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150367

프로그래머스

해당 문제를 해결하기 위한 절차는 다음과 같다.

1. 우선 주어진 10진수를 2진수로 변환하여준다.

2. 변환된 모든 수가 바로 포화 이진트리로 만들 수 없기 때문에 로그를 사용하여 해당 수로 만들 수 있는 포화 이진트리의 노드 수를 구해주어서 부족한 부분을 '0'으로 채워준다.

3. 포화 이진트리의 조건에 맞지 않는 경우는 조상이 0인 상태에서 자식이 1인 경우이다.

4. 3번에 해당하는 경우가 있는지, 재귀 함수를 통해서 판별한다.

import math

def dfs(now, prev):
    mid = len(now)//2
    if now:
        if now[mid] == '1': # 이 경우, 자식을 나타내고 있지만, 다음 재귀 호출에서의 값은 조상을 나타낸다.
            son = True
        else:
            son = False
    else:
        return True
    
    if son and not prev: # 조상이 0이고 자식이 1인 경우, 이진트리의 조건에 부합하지 않으므로 거짓을 반환한다.
        return False
    
    return dfs(now[mid+1:], son) and dfs(now[:mid], son) # 루트 노드를 기준으로 좌우로 분리하여 재귀호출을 실행한다.

def solution(numbers):
    answer = []
    binary = []
    
    for number in numbers:
        temp = bin(number)[2:]
        length = 2**int(math.log(len(temp), 2)+1)-1
        temp = '0'*(length-len(temp))+temp
        binary.append(temp)
    
    for i in binary:
        if i == '1':
            answer.append(1)
        elif i[len(i)//2] == '1' and dfs(i, True):
            answer.append(1)
        else:
            answer.append(0)
    
    return answer

아래는 해당 코드를 작성하는 과정에서 필자가 실수한 부분이다.

def dfs(now, prev):
    mid = len(now)//2
    if now:
        if now[mid] == '1':
            son = True
        else:
            son = False
    else:
        return True
    
    if son and not prev:
        return False
    
    return dfs(now[mid:], son) and dfs(now[:mid+1], son)

# 정답코드
	return dfs(now[mid+1:], son) and dfs(now[:mid], son)

바로 재귀호출에서의 인덱스 설정을 잘못한 것이다.

처음에는 maximum recrusion 에러가 발생하였다.

알고보니 !

다음 재귀 호출을 할 때는 루트 노드를 기준으로 좌, 우의 트리를 넣어주어야한다.

즉, 기존의 루트 노드는 제외해야한다는 것이다.

하지만 오답 코드는 now[mid:](우), now[:mid+1](좌)를 설정하여 루트 노드를 포함한 채로 계속 똑같은 코드를 호출하는 것이다.

따라서, 동일한 값이 무한으로 반복되는 오류가 발생하였다.

인덱스 하나의 실수로 전체의 점수를 날린다고 생각하니, 간담이 서늘할 지경이다.

코드를 작성할 때, 하나하나 꼼꼼히 체크하는 습관을 기르도록 하자 !