[자바] 백준 1990 - 소수인팰린드롬 (java)

 문제 : boj1990

---

 

필요 알고리즘 개념

• 소수 판정, 에라토스테네스의 체
  
  • 팰린드롬도 판정해야하지만, 그보다 먼저 소수 판정을 할 수 있어야 한다. 에라토스테네스의 체를 알고 있어야 1억 이하의 소수를 효율적으로 구할 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

1. b 이하의 소수를 모두 구한다.

  에라토스테네스의 체를 사용해 구해주면 된다. 이 때 sqrt(b) 까지만 확인해주면 된다. (에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유)

  코드에서는 getPn() 이 이 역할을 한다.

 

2. '1'에서 구한 소수 중 팰린드롬인 수를 찾는다.

  isPalindrome()이 해당 역할을 한다. 굳이 int형 자체로 팰린드롬 판정 하겠다고 좀 복잡해졌는데, 어차피 최대 8자리 수밖에 안되므로 그냥 String으로 바꾼 후 reverse 후 원본과 동일한지 보자.

 

3. '1'과 '2'를 미리 전처리 해서 코드에 담아도 가능하다.ㅋㅋㅋㅋ

 

4. 어차피 전처리한 결과가 팰린드롬인 수 이므로 절반까지만 전처리해도 된다! (e.g. 3589853 -> 3589. 이후 사용 시 3589853으로 원복)

 

 

아래부터 '1', '2'로 정상적으로 푼 것, 중간은 '3', 맨 위는 '4' 이다. 맨 아래에서 중간은 코드 길이가 너무 늘어났고, 맨 아래에서 맨 위로는 메모리 1/22배, 시간 1/19배, 코드 길이 2.6배. 만-족

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private ArrayList<Integer> getPn(int limit) {
        ArrayList<Integer> pn = new ArrayList<>();
        boolean[] isPn = new boolean[limit+1];
        int sqrtN = (int)Math.sqrt(limit);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= limit) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= limit; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
        return pn;
    }
    
    private boolean isPalindrome(int num) {
        int base = 1;
        int len = 0;
        while (num >= base) {
            base *= 10;
            len++;
        }
        int low = 10;
        int high = base/10;
        for (int i = 0; i < len/2; i++, low*=10, high/=10)
            if ((num%low)/(low/10) != (num/high)%10) return false;
        return true;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        ArrayList<Integer> pn = getPn(b);
        for (int cur : pn) {
            if (cur < a) continue;
            if (isPalindrome(cur))
                sb.append(cur).append('\n');
        }
        sb.append(-1);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}