이 문제에서는 주어진 수 N보다 크거나 같은 수 중에서 가장 작은 소수 회문(Prime Palindrome)을 찾아야 합니다. 회문이란 앞에서 읽으나 뒤에서 읽으나 같은 수를 의미하며, 소수 회문은 그 수가 동시에 소수이기도 한 경우를 말합니다.
예를 들어 N이 13이라면, 13 이상의 수 중에서 가장 작은 소수 회문은 101입니다. 13 자체는 회문이 아니고, 그 다음 회문들인 22, 33 등은 소수가 아니기 때문입니다.
해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 만약 N이 8 이상 11 이하라면, 바로 11을 반환합니다. (8~11 사이에는 소수 회문이 존재하지 않기 때문입니다.)
- i를 1부터 99999까지 반복합니다.
- s := i를 문자열로 변환
- r := s를 복사한 후 뒤집기(reverse)
- num := s와 r의 두 번째 문자부터 끝까지의 부분 문자열을 이어 붙인 후 숫자로 변환 — 이렇게 하면 홀수 길이의 회문이 만들어집니다.
- 만약 num이 N보다 크거나 같고, 동시에 소수라면 num을 반환합니다.
- 조건을 만족하는 수를 찾지 못하면 0을 반환합니다.
여기서 핵심 아이디어는 회문을 처음부터 하나씩 검사하는 대신, 앞부분 숫자를 정하고 거울처럼 대칭되는 형태로 회문을 직접 생성하는 것입니다. 이렇게 하면 모든 수를 일일이 확인하는 것보다 훨씬 효율적으로 소수 회문을 탐색할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPrime(int n){
if(n % 2 == 0 && n > 2) return false;
for(int i = 3; i * i <= n; i++){
if(n % i == 0) return false;
}
return n != 1 && n != 0;
}
int primePalindrome(int N) {
if(8 <= N && N <= 11) return 11;
for(int i = 1; i < 100000; i++){
string s = to_string(i);
string r = s;
reverse(r.begin(), r.end());
int num = stoi(s + r.substr(1));
if(num >= N && isPrime(num)) return num;
}
return 0;
}
};
main(){
Solution ob;
cout << (ob.primePalindrome(105));
}입력
105
출력
131
위 예제에서 입력값이 105일 때, 출력 결과는 131입니다. 131은 앞뒤가 같은 회문이면서 동시에 소수이며, 105 이상인 수 중에서 조건을 만족하는 가장 작은 수이기 때문입니다.