알고리즘 챌린지 8일차

문제

문제: 백준 알고리즘 1747번 소수&팰린드롬

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[10000001];        //N의 범위까지 소수 구하기
        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 = j + i) {  //배수 지우기
                A[j] = 0;
            }
        }
        int i = N;
        while (true) {  //N부터 1씩 증가시키면서 소수와 펠린드롭 수가 맞는지 확인하기
            if (A[i] != 0) {
                int result = A[i];
                if (isPalindrome(result)) {
                    System.out.println(result);
                    break;
                }
            }
            i++;
        }
    }

    private static boolean isPalindrome(int result) { //펠린드롬 수 판별 함수
        char temp[] = String.valueOf(result).toCharArray();
        int s = 0;
        int e = temp.length - 1;
        while (s < e) {
            if (temp[s] != temp[e]) {
                return false;
            }
            s++;
            e--;
        }
        return true;
    }
}

풀이

에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후 이 소수들의 집합에서 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아내면 되는 문제이다.

• 인덱스를 자신의 값으로 초기화한다.
• 제곱근까지만 수행하면서 배수를 지운다.(소수만 남기기)
• N부터 1씩 증가하면서 펠린드롬 수가 맞는지 확인한다.
• 투포인터를 활용하여 단어의 시작과 끝에서 출발해 각 인덱스가 다르면 false를 리턴한다.

후기

N의 최대 범위가 1000000이므로 배열의 크기를 넉넉하게 해줘야한다. 1000000일 경우에는 1003001이므로 배열의 크기를 1003002로 지정해주면 좋다. 투포인터 부분의 경우는 reverse를 이용하여 원래 문자열과 equals로 판별해도 된다. 입력값의 최대는 출력값의 최대가 아닌것을 유의하자!