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

rhkr9080·2023년 6월 24일

프로그래머스

목록 보기

4/19

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

💻 문제 풀이 : C++

def makeBinaryNumber(number):
    reverseBinaryNumber = []
    while number != 1:
        reverseBinaryNumber.append(str(number % 2))
        number //= 2
    reverseBinaryNumber.append("1")
    binaryNumber = ''.join(reverseBinaryNumber[::-1])
    binaryTreeSize = 1
    # 강제로 포화이진트리로 만들어줌!!
    while binaryTreeSize < len(binaryNumber):
        binaryTreeSize = (binaryTreeSize + 1) * 2 - 1
    binaryNumber = "0" * (binaryTreeSize - len(binaryNumber)) + binaryNumber
    return binaryNumber

# 재귀 Dec to Bin
def dec2bin(number):
    if (number // 2 == 0):
        return str(number % 2)
    return dec2bin(number//2) + str(number % 2)

def isPossible(start, end, binStr):
    if start == end:
        return binStr[start]
    mid = (start + end) // 2
    left = isPossible(start, mid - 1, binStr)
    if not left or (binStr[mid] == "0" and left == "1"): return False
    right = isPossible(mid + 1, end, binStr)
    if not right or (binStr[mid] == "0" and right == "1"): return False
    if (left == "0" and right == "0" and binStr[mid] == "0"): return "0"
    return "1"

def solution(numbers):
    answer = []
    for number in numbers:
        num_str = ""
        # 단순히 홀짝만 맞춘다고 해결이 되지 않음!!
        # => 재귀에서 포화이진트리를 가정하기 때문!
        # if(len(dec2bin(number)) % 2 == 0):
        #     num_str = "0" + dec2bin(number)
        # else:
        #     num_str = dec2bin(number)
        num_str = makeBinaryNumber(number)
        # print(num_str)
        if isPossible(0, len(num_str)-1, num_str):
            answer.append(1)
        else:
            answer.append(0)
    
    return answer

ref)
https://velog.io/@yhnb3/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%91%9C%ED%98%84-%EA%B0%80%EB%8A%A5%ED%95%9C-%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC

📌 memo