[프로그래머스][Python] 2023 KAKAO BLIND RECRUITMENT : 표현 가능한 이진트리

1일 1PS 31일차!

📚 문제

---

Lv 3

• 이진트리를 만들고 아래에서부터 검사해나가면 된다.
• 실제 이진트리를 만들었을 때,
  • 1 or 3 이 존재하면 2 가, 5 or 7 이 존재하면 6이 존재해야한다.
  • 2 or 6 이 존재하면 4가 존재해야한다.
• 가장 아래단부터
  • (1, 3), (5, 7), (7, 9) …
  • 홀수 두 개씩 검사하며 둘 중 하나가 1일 경우 둘의 평균값인 짝수도 1이어야한다.
• 아래에서 두 번째는
  • (2, 6), (10, 14) …
  • 4 차이를 두고 검사한다.
• 결국 단이 올라갈 수록 2의 거듭제곱의 차이만큼 검사해야하며, 시작하는 값 또한 1, 2, 4 .. 등 2의 거듭제곱이다.

💡 풀이과정

---

1. 숫자를 2진수로 변환한다.
2. 변환된 2진수를 이진트리를 검사할 수 있도록 길이를 2^n - 1 형태로 맞춰준다.
3. 가장 아래부터 가장 위까지 검사해나간다.

💻 코드

---

def solution(numbers):
    answer = []
    for num in numbers:
        n = bin(num)[2:]
        fill = 1
        cnt = 0
        while fill <= len(n):
            fill *= 2
            cnt += 1
        n = n.zfill(fill - 1 )
        if n == '0':
            flag = False
        else:
            flag = True

        for i in range(cnt - 1):
            if flag:
                r = 2**(i + 1)
                temp = 2**i
                while temp <= fill:
                    if n[temp - 1] == '1' or n[temp + r - 1] == '1':
                        if n[int(temp + r/2 - 1)] == '0':
                            flag = False
                            break
                    temp += r*2

        if flag:
            answer.append(1)
        else:
            answer.append(0)

    return answer