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
}