https://www.acmicpc.net/problem/1747

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

예제 입출력

• 예제 입력 1

31

• 예제 출력 1

101

Solution

#include <iostream>
#define MAX 1004000
using namespace std;

int arr[MAX];

bool isPalindrom(int inputData){
    string str = to_string(inputData);
    for(int i = 0; i < str.size() / 2; i++){
        if(str[i] != str[str.size() - i - 1]) {
            return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    for(int i = 1; i <= MAX; i++) arr[i] = i;

    for(int i = 2; i * i <= MAX; i++) {
        if(arr[i] == -1) continue;
        for(int j = i * 2; j <= MAX; j += i){
            arr[j] = -1;
        }
    }
    arr[0] = arr[1] = -1;

    int N; cin >> N;
    for(int i = N; i <= MAX; i++){
        if(arr[i] != -1){
            if(isPalindrom(arr[i])){
                cout << arr[i];
                break;
            }
        }
    }
    return 0;
}

오랜만에 돌아왔다. 대회 준비할 겸, 오래 쉰 알고리즘 공부 다시 시작할 겸...
사실 문제는 별거 없다. 에라토스테네스의 체만 쓸 줄 알면 풀 수 있다.

for(int i = 1; i <= MAX; i++) arr[i] = i;

for(int i = 2; i * i <= MAX; i++) {
    if(arr[i] == -1) continue;
    for(int j = i * 2; j <= MAX; j += i){
        arr[j] = -1;
    }
}
arr[0] = arr[1] = -1;

일단 주의해야 할 점은 입력 값의 범위가 0 이상 1000000 이하라는 것이다.
즉 입력값에 0을 집어넣을 수도 있다는 것.
0을 넣는 경우를 간과했다가 문제가 터져버렸다. (많이 퇴화했다. 거의 두달을 접으니까 이런 일도 벌어진다...)
가능한 모든 경우에 대해 소수 값만 남기고 모두 -1로 처리해버린다. 어차피 소수라는 조건이 걸려야만 이게 펠린드롬인지 아닌 지 구하든 말든 할 테니까.

bool isPalindrom(int inputData){
    string str = to_string(inputData);
    for(int i = 0; i < str.size() / 2; i++){
        if(str[i] != str[str.size() - i - 1]) {
            return false;
        }
    }
    return true;
}

펠린드롬 구하는 방법은 간단하다. 그냥 문자열로 변환해서 앞뒤를 비교해주면 그만이다.
비교하는 방법은 여러가지가 있다. 이렇게 그냥 i 인덱스 하나로 구하는 방법도 있고 투포인터 마냥 left, right로 나누어서 찾는 법도 있다.

어떻게 풀든 비슷하니 이 부분은 자유롭게.

오랜만에 알고리즘 공부를 다시 하니 뇌가 다시 깨어나는 기분이다. 너무 오래 접기도 했고...계속 공부 해 나가야 하는 개발자의 삶인데 나태지옥에 있을 수는 없지 않겠는가.