[Do It! 코딩테스트 자바편(김종관)] 문제 039(백준 1747번)

난이도

크게 어렵지 않은 문제. 물론 나는 초보라서 교재 설명을 힌트삼아서 보고 풀었다. 그래도 이해하는 데 전혀 어렵지 않은 문제

문제

소수&팰린드롬 수 중에서 최솟값 찾기(백준: 1747번)

풀이

• 배열 크기를 얼마로 잡을지 고민. 이건 딱히 정답 없고, 크기 적당히 감으로 잡은 다음에 돌려봐서 실패하면 그 때 사이즈 더 키우는 식으로 하면 될 듯함.
• 왜냐면 다른 사람 풀이 보면 제각각임. 어떤 사람은 1,004,000으로, 책에서는 10,000,000으로 잡았다. 보니까 1,000,000 이상의 수에서 소수이면서 팰린드롬 수의 최솟값은 1,003,001이라고 보았다. 따라서 나는 이걸 기준으로 사이즈를 잡았다.

import java.util.Scanner;

public class Main {
    static int size = 1003001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[size + 1];
        for (int i = 2; i < a.length; i++)
            a[i] = i;

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

        int result = minimunPalindrome(a, n);
        System.out.println(result);
        sc.close();

    }

    static int minimunPalindrome(int[] a, int startNum) {
        for (int i = startNum; i < a.length; i++) {
            if (a[i] == 0)
                continue;

            char[] temp = Integer.toString(a[i]).toCharArray();
            int s = 0;
            int e = temp.length - 1;
            boolean res = true;

            while (s < e) {
                if (temp[s] != temp[e]) {
                    res = false;
                    break;
                }
                s++;
                e--;
            }

            if (res == true)
                return a[i];
        }
        return -1;
    }
}