[코딩테스트] 🐷 포현 가능한 이진 트리 - KAKAO 2023

문제링크

문제링크

난이도

프로그래머스 3

유형

구현, 이진트리

소요시간

1시간 이상 못풀어서 해설 봄
https://www.youtube.com/watch?v=8vziZJKLv-Y

회고

문제 자체를 이해를 못했다. 예시 문제의 7은 이해가 갔는데 42부터 이해가 안 가서 고민하다가, 답이 없을 것 같아서 해설을 봤음

1. 이진 수를 만들고

2. 포화 이진 트리가 되도록 앞에 0을 추가

3. 해당 수가 포화 이진트리로 그릴 수 있는지 로직 구현

4. 이진 트리 순회로 판단

코드

func solution(_ numbers: [Int64]) -> [Int] {
    var answer = [Int]()

    numbers.forEach { i in

        // 1. Binary
        var binary = String(i, radix: 2)

        // 2. 포화 이진 트리될 때까지 0붙이기
        var n: Double = 0

        while Int(Double(pow(2, n))) - 1 < binary.count {
            n += 1
        }
        let treeSize = Int(Double(pow(2, n))) - 1

        while treeSize > binary.count {
            binary = "0" + binary
        }

        answer.append(isBinaryTree(binary))
    }

    return answer
}

func isBinaryTree(_ i: String) -> Int {

    let mid = i.count / 2
    let midIndex = i.index(i.startIndex, offsetBy: mid)
    let parent = i[midIndex]

    let left = i[i.startIndex..<midIndex]
    let leftMidIndex = left.index(left.startIndex, offsetBy: mid / 2)

    let right = i[i.index(after: midIndex)..<i.endIndex]
    let rightMidIndex = right.index(right.startIndex, offsetBy: mid / 2)

    // root가 0일 때 자식 노드가 1일 수 없음
    if parent == "0" && (left[leftMidIndex] == "1" || right[rightMidIndex] == "1") {
        return 0
    }

    // 왼쪽 자식 서브 트리 재귀
    if left.count >= 3 {
        if isBinaryTree(String(left)) == 0 {
            return 0
        }
    }

    // 오른쪽 자식 서브 트리 재귀
    if right.count >= 3 {
        if isBinaryTree(String(right)) == 0 {
            return 0
        }
    }

    return 1
}