Leetcode 를 풀어 보았다.

Pick one 버튼을 눌러 랜덤으로 문제를 하나 골랐다.

906. Super Palindromes

[left, right] 사이에 N 과 N*N 이 모두 팰린드롬인 수의 갯수를 구하는 문제인 듯 하다.

right < 1e18 이므로 가능한 N < 1e9 이다.

1e9 개의 팰린드롬을 미리 만들어 놓고 제곱수도 팰린드롬인지 확인하기로 한다.

자릿수가 n 이하인 팰린드롬 만드는 시간 복잡도는 양쪽에 숫자를 갖다 붙이는 방법으로 하면 O(10^(n/2)) 이다.

이 때 만들어진 팰린드롬 개수도 동일하고, 자릿수가 n 이하인 숫자가 팰린드롬인지 확인하는 시간 복잡도는 O(n) 이므로 시간은 충분하다.

func superpalindromesInRange(_ left: String, _ right: String) -> Int {
    var p = (1...9).map { "\($0)" }
    var res = 0

    for i in 1..<Int(1e4) {
        let s = "\(i)", r = String(s.reversed())
        for j in (0..<10).map { "\($0)" } + [""] {
            p.append(s + j + r)
        }
    }

    for n in p.map { Int($0)! * Int($0)! } {
        if Int(left)! <= n, Int(right)! >= n {
            var s = "\(n)", r = String(s.reversed())
            res += s == r ? 1 : 0
        }
    }

    return res
}