[프로그래머스]유사 칸토어 비트열(Swift) - Recursion

• 시간 초과

func solution(_ n:Int, _ l:Int64, _ r:Int64) -> Int {
    let l: Int = Int(l) - 1
    let r: Int = Int(r) - 1

    func cantor(n: Int) -> String {
        if n == 0 { return "1" }
        var dp: [String] = ["1"]
        for i in 0..<n {
            var arr: String = ""
            for c in Array(dp[i]) {
                if c == "1" {
                    arr.append("11011")
                } else {
                    arr.append("00000")
                }
            }
            dp.append(arr)
        }
        print(dp)
        return dp[n]
    }

    return Array(cantor(n: n))[l...r]
        .filter { $0 == "1" }
        .count
}

• 재귀 함수

func solution(_ n:Int, _ l:Int64, _ r:Int64) -> Int {
    let l: Int = Int(l)
    let r: Int = Int(r)
    let arr: [Int] = [1, 1, 0, 1, 1]

    func countOne(_ boundary: Int) -> Int {
        if boundary <= 5 { return arr[0..<boundary].reduce(0, +) }
        
        var base = 1
        while Int(pow(Double(5), Double(base+1))) < boundary {
            base += 1
        }
        
        let section = boundary / Int(pow(Double(5), Double(base)))
        let remainder = boundary % Int(pow(Double(5), Double(base)))
        
        var answer = section * Int(pow(Double(4), Double(base)))
        
        if section >= 3 {
            answer -= Int(pow(Double(4), Double(base)))
        }
        
        if section == 2 {
            return answer
        } else {
            return answer + countOne(remainder)
        }
    }

    return countOne(r) - countOne(l-1)
}