[BOJ/백준] 1747번 : 소수&팰린드롬 (C++)

[BOJ/백준] 1747번 : 소수&팰린드롬

BOJ 1747

문제 해석

• 에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후 이 소수들의 집합에서 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아내면 되는 문제다.
• 팰린드롬 수 판별 시에 숫자를 char 배열 형태로 구현하여 판별하면 된다고 생각했다.

풀이

• 첫번째 에라토스테네스의 체를 이용하여 소수를 구한다. 주어진 수 N부터 10000000 사이의 수 중에서 소수들만 배열에 따로 모아놓는다.

• 그리고 팰린드롬 수인지 판별하는 함수를 만들어서 각 배열을 인덱스로 접근하면서 하나하나 확인해본다.

• 팰린드롬 수인지 판별하는 함수는 먼저 숫자를 배열의 형태로 구현하고난 뒤, start와 end 포인터 (투포인터)를 이용하여서 두 값을 비교해 같으면 start++, end– 연산으로 두 포인터를 이동시킨다. start < end를 만족할 때까지 반복해 모든 값이 같으면 팰린드롬 수로 판별한다. 아래는 팰린드롬 수 판별하는 함수이다.

bool isPalindrome(int target) {
    string temp_str = to_string(target);//숫자를 문자열로 반환
    int s = 0;
    int e = temp_str.size() - 1;

    while (s < e) {
        //start와 end의 값이 다르면 바로 false 반환
        if (temp_str[s] != temp_str[e]) return false;
        s++;//같다면 start++
        e--;//end--
    }//이상 없이 while문을 빠져나왔으면 팰린드롬 수
    return true;
}

코드

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

bool isPalindrome(int target);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long N;
    cin >> N;

    // 동적 배열로 소수 판별 배열 생성
    vector<long> A(10000001, 0);

    // 에라토스테네스의 체 초기화
    for (int i = 2; i < 10000001; i++) {
        A[i] = i;
    }

    for (int i = 2; i <= sqrt(10000001); i++) {
        if (A[i] == 0) continue;
        for (int j = i + i; j < 10000001; j += i) { // i의 배수만 제거
            A[j] = 0;
        }
    }

    // 입력값 N 이상의 소수 중 가장 작은 팰린드롬 수 찾기
    int i = N;

    while (true) {
        if (A[i] != 0) { // 소수일 경우
            int result = A[i];
            if (isPalindrome(result)) { // 팰린드롬 여부 확인
                cout << result << "\n";
                break;
            }
        }
        i++;
    }

    return 0;
}

// 팰린드롬 확인 함수
bool isPalindrome(int target) {
    string temp_str = to_string(target);
    int s = 0;
    int e = temp_str.size() - 1;

    while (s < e) {
        if (temp_str[s] != temp_str[e]) return false;
        s++;
        e--;
    }
    return true;
}