[백준] 1747번 : 소수&팰린드롬 – JAVA [자바]

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

1747번: 소수&팰린드롬

 

---

• 문제

 

 

---

• 문제 풀이

백준 1747번 소수&팰린드롬은 실버 1 난이도의 수학 및 에라토스테네스의 체 문제이다.

 

이 문제에서는 정수 N이 주어진다. 그리고 N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서 가장 작은 수를 출력하면 된다.

 

이 문제에서 중요한 포인트는 바로 소수 찾기와 팰린드롬인지 확인하는 것이다. 이 문제에서는 한 숫자가 소수인지 아닌지를 구하는 게 아닌 다수의 소수를 구하고 이 소수들이 팰린드롬인지 아닌지를 확인하는 게 필요하므로 에라토스테네스의 체 알고리즘을 사용해야 한다.

 

에라토스테네스의 체는 소수 판별 알고리즘이다. 이 글에서 설명이 되어 있기 때문에 잘 모른다면 참고하면 되겠다.

 

[알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes)

 

우선 N의 범위가 1,000,000까지 이므로 사이즈가 이것의 10배인 배열을 만든다. 그리고 에라토스테네스의 체 알고리즘을 이용해서 N보다 크거나 같은 소수들을 구하고 리스트에 저장해준다. 

 

이 과정을 거치면 리스트에 소수들이 있을 것이다. 이제 이 소수들이 팰린드롬인지 아닌지 확인을 하고 맞다면 출력을 하면 된다. 

 

우선 팰린드롬은 거꾸로 읽어도 똑같은 숫자다. 예를 들어서 121이 있다. 똑바로 읽던 거꾸로 읽던 121이다.

 

즉, 이 숫자를 거꾸로 한게 같으면 팰린드롬이 된다. 

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

import java.io.*;
import java.util.*;

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

        // 배열 arr의 크기를 10000001로 설정하고, boolean 타입 배열로 소수를 표시하는 방법을 사용한다.
        boolean[] arr = new boolean[10000001];

        // 소수를 담을 리스트
        List<Integer> list = new ArrayList<>();

        // 에라토스테네스의 체 알고리즘을 이용하여 소수를 구하고, 소수 중 팰린드롬인 수를 찾는다.
        for (int i = 2; i <= arr.length - 1; i++) {
            // i가 n 이상이고, 아직 소수로 판별되지 않은 경우 리스트에 추가한다.
            if (i >= n && !arr[i])
                list.add(i);

            // i의 배수들을 소수에서 제외하기 위해 arr 배열에서 true로 표시한다.
            for (int j = i + i; j <= 10000000; j += i) {
                arr[j] = true;
            }
        }

        // 리스트에 있는 소수들을 순회하면서 팰린드롬인 수를 출력한다.
        for (int i : list) {
            String num = String.valueOf(i);
            String reversed = new StringBuilder(num).reverse().toString();

            // num과 reversed가 같으면 팰린드롬인 수이므로 출력하고 종료한다.
            if (num.equals(reversed)) {
                System.out.println(num);
                return;
            }
        }
    }
}