[알고리즘] 1747번

오늘 풀어볼 문제는 백준 1747번 문제 "소수&팰린드롬" 이다.

이 문제는 실버1 문제이고 정수론 문제이다.

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

📌첫 번째 도전📌
위 문제는 앞에서 풀었던 문제들을 활용하여 배열에 소수의 값들을 모두 넣어줬다. 그 후 배열의 값을 매 반복문마다 String으로 변경하고 while을 통해 팰린드롬인지 비교하였다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        long[] arr = new long[10000001];

        for(int i=2; i<arr.length; i++) {
            arr[i] = i;
        }

        for(int i = 2; i <= Math.sqrt(arr.length); i++) {
            if(arr[i] == 0) {
                continue;
            }
            for(int j = i + i; j < arr.length; j = j+i) {
                arr[j] = 0;
            }
        }

        for(int i=N; i<=arr.length; i++) {
            String str = Long.toString(arr[i]);
            int start_index = 0;
            int end_index = str.length() - 1;
            boolean check = true;

            if(!str.equals("0")) {
                while(start_index < end_index) {
                    if(str.charAt(end_index) != str.charAt(start_index)) {
                        check = false;
                    }
                    start_index++;
                    end_index--;
                }

                if(check == true) {
                    System.out.println(str);
                    break;
                }
            }
        }
    }
}

[문제 출처] : https://www.acmicpc.net/problem/1747