슈퍼 팰린드롬(superpalindrome)은 자기 자신이 회문(palindrome)일 뿐만 아니라, 어떤 회문의 제곱이기도 한 양의 정수를 의미합니다. 이번 글에서는 두 개의 양의 정수 L과 R이 주어졌을 때, 닫힌 구간 [L, R] 안에 포함된 슈퍼 팰린드롬의 개수를 찾는 방법을 살펴보겠습니다.
예를 들어 입력이 L = 5, R = 500이라면 출력은 3이 됩니다. 이 범위 내의 슈퍼 팰린드롬은 9, 121, 484입니다.
- 9 = 3² → 3과 9 모두 회문
- 121 = 11² → 11과 121 모두 회문
- 484 = 22² → 22와 484 모두 회문
접근 방법
[L, R] 범위의 모든 수를 하나씩 검사하는 것은 비효율적입니다. 대신, 회문이 되는 수를 직접 생성한 뒤 그 제곱이 회문인지 확인하는 재귀적 방식을 사용하면 훨씬 빠르게 답을 구할 수 있습니다. 알고리즘은 다음 단계로 진행됩니다.
- helper(x, m, M, lb, ub) 함수를 정의합니다.
- x > ub이면 함수를 종료(return)합니다.
- x ≥ lb이고 x × x가 회문이라면 정답 카운터(ans)를 1 증가시킵니다.
- i := 1부터 시작하여 m + 2 × i ≤ M을 만족하는 동안 i를 증가시키며 반복합니다.
- W := 10^(m + 2 × i − 1)
- w := 10^i
- z를 1부터 9까지 증가시키며 helper(z × W + x × w, m + 2 × i, M, lb, ub)를 재귀 호출합니다.
메인 메서드의 처리 과정
- lb := √L, ub := √R 을 계산합니다.
- M := log₁₀(ub) + 1 을 계산합니다.
- z를 0부터 9까지 증가시키며 다음 두 함수를 호출합니다.
- helper(z, 1, M, lb, ub)
- helper(11 × z, 2, M, lb, ub)
- 최종적으로 ans를 반환합니다.
다음 구현 예제를 통해 더 잘 이해할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
int ans = 0;
public:
int superpalindromesInRange(string L, string R){
long double lb = sqrtl(stol(L)), ub = sqrtl(stol(R));
int M = log10l(ub) + 1;
for (int z = 0; z <= 9; z++) {
helper(z, 1, M, lb, ub);
helper(11 * z, 2, M, lb, ub);
}
return ans;
}
private:
void helper(long x, int m, int M, long double lb, long double ub){
if (x > ub)
return;
if (x >= lb && is_palindrome(x * x))
ans++;
for (int i = 1; m + 2 * i <= M; i++) {
long W = powl(10, m + 2 * i - 1) + 1;
long w = powl(10, i);
for (int z = 1; z <= 9; z++)
helper(z * W + x * w, m + 2 * i, M, lb, ub);
}
}
bool is_palindrome(long x){
if (x == 0)
return true;
if (x % 10 == 0)
return false;
long left = x, right = 0;
while (left >= right) {
if (left == right || left / 10 == right)
return true;
right = 10 * right + (left % 10), left /= 10;
}
return false;
}
};
main(){
Solution ob;
cout << (ob.superpalindromesInRange("5", "500"));
}
입력
"5", "500"
출력
3