[프로그래머스] 표현 가능한 이진트리 (Python, 2023 카카오 blind recruitment)

프로그래머스

 

---

 

☁️ 문제 설명

• 입력으로 주어진 숫자가 이진트리로 표현이 가능하면 1, 불가능하면 0
• 이진트리를 수로 표현하는 방법
  • 1. 주어진 이진트리에 더미 노드 추가해 포화 이진트리로 만들기
  • 2. 포화 이진트리를 중위 순회로 살펴봄
  • 3. 살펴본 노드가 더미 노드면 0 추가, 더미 노드 아니면 1 추가
  • 4. 문자열에 저장된 이진수를 십진수로 변환

 

☁️ 입출력

• 입력: `numbers`, 
  • numbers 예시: [7, 42, 5]
• 출력: `result`
  • result 예시: [1,1,0]

 

☁️ 제한 사항

• 1 <= numbers의 길이 <= 10,000
  • 1 <= numbers의 원소 <= 10^15

---

💡 문제 풀이 아이디어

• 1) 입력에 제시된 숫자를 이진수로 변환
• 2) 이진수로 변환하고 포화 이진트리로 만들기 위해 2k+1의 길이로 변환(zfill 사용)
• 3) left, mid, right로 나눠가며 재귀 함수로 `root==0`인지 확인

 

🚨 주의할 점

• 문제는 이진트리에서 수를 만드는 방법으로 설명되어 있어 주어진 이진트리가 없어서 혼동이 올 수 있는데, 주어진 수를 이진수로 변환하고 이진수를 이진트리로 만드는 순서로 생각하면 풀기 수월해짐
• 재귀 함수를 통해 root가 0인지 아닌지 확인하는 방법을 떠올려야 함
• 저는 처음에 입출력 예시에 있는 숫자들만 보고 단순하게 '짝수 인덱스에 0이 있으면 이진트리 표현이 불가능하구나!'라고 생각하고 코드 작성했다가 틀렸답니다

---

💻 코드

def check(b):
    mid = len(b) // 2
    root = b[mid]
    
    if len(b) == 1:
        return True
    
    left = b[:mid]
    right = b[mid+1:]
    
    if root == '0' and ('1' in left or '1' in right):
        return False
    
    return check(left) and check(right)

def solution(numbers):
    answer = []
    
    for number in numbers:
        flag = True
        binary = bin(number)[2:]
        
        length = 1
        while length < len(binary):
            length = length * 2 + 1
        binary = binary.zfill(length)
        
        if check(binary):
            answer.append(1)
        else:
            answer.append(0)
    
    return answer