문제 링크

카카오 코딩테스트: 표현 가능한 이진트리

문제 분석

이 문제는 구현 문제

  1. 먼저 십진수를 이진수로 변환한다.
  2. 포화이진트리의 정점의 개수는 2^k - 1 이다. 만약 이진수의 자릿수가 6이고, 포화이진트리는 7이라면, 1개의 0을 이진수 문자열에 붙여준다.
  3. 포화이진트리를 보면, 루트노드는 항상 왼쪽 서브트리의 루트노드와 오른쪽 서브트리의 루트노드의 딱 중간이다. 그렇기 때문에, 재귀함수로 f(start, end) 이분탐색을 구현한다.
  4. 만약 101 처럼 루트노드가 0인데, 자식노드 중에 1인 것이 하나라도 있다면, 그 숫자는 포화이진트리로 표현할 수 없다. 따라서 false를 리턴한다.

내 코드

import Foundation

func solution(_ numbers:[Int64]) -> [Int] {
    
    func go(_ arr: [Character], _ l: Int, _ r: Int) -> Bool {
        if l > r { return true }
        let mid = (l + r) / 2
        if arr[mid] == "0" {
            for i in l...r {
                if arr[i] == "1" { return false }
            }
            return true
        }
        return go(arr, l, mid - 1) && go(arr, mid + 1, r)
    }
    
    func solve(_ num: Int64) -> Bool {
        var binary = String(num, radix: 2)
        var k = 1
        while (1 << k) - 1 < binary.count { k += 1 }
        // 왼쪽에 필요한만큼 0 추가 (포화이진트리로 만들기)
        let zeroCnt = ((1 << k) - 1) - binary.count
        binary = String(repeating: "0", count: zeroCnt) + binary
        return go(Array(binary), 0, binary.count - 1)
    }
    return numbers.map { solve($0) ? 1 : 0 }
}

배운 점

리팩토링 코드

정리