백준 1747 자바 - 소수&팰린드롬 (BOJ 1747 JAVA)

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

 

 

풀이1

  다소 어려워보일 수 있으나, 문제에서 원하는 부분을 순서대로 구현하면 어렵지 않다.

 

1. 소수를 알 수 있어야 한다. 이때, N은 최대 100만인데 문제에서 요구하는 것은 N 보다 '큰거나 같은 수'중 소수이면서 팰린드롬인 수 이므로 100만까지만 소수를 구해서는 안된다. 약간 범위를 늘려봐서 확인해보면 되는데, 결론적으로 1,003,001 까지 확인해보면 모든 입력에 대해 만족할 수 있다. 소수를 구하는 것은 에라토스테네스의 체를 사용하면 된다. 

 

2. 소수 중 팰린드롬인 수를 알 수 있어야 한다. 숫자 자체로 맨앞과 맨뒤 문자열을 비교하며 중간까지 와도 되는데, 중간에서 멈추기가 좀 어렵다. 어차피 최대 100만 근처의 작은(?) 수 이므로, 문자열로 그냥 변경하고 팰린드롬인지 직접 확인해보면 된다.(코드의 isPalindrome())

 

3. 이제 N을 입력받고, '1'과 '2'의 과정을 거쳐 나온 소수이면서 팰린드롬인 1003001이하의 수 중 N보다 크거나 같은 작은 작은수를 출력해주면 된다.

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01700/BOJ_1747.java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final int MAX = 1003001;
    boolean[] arr;

    private boolean isPalindrome(int pn) {
        String tmp = String.valueOf(pn);
        for (int i = 0; i < tmp.length()/2; i++) {
            if (tmp.charAt(i) != tmp.charAt(tmp.length()-1-i))
                return false;
        }
        return true;
    }

    private void initPnAndPalindrome() {
        arr = new boolean[MAX+1];
        for (int i = 2; i <= Math.sqrt(MAX); i++) {
            int base = i;
            while ((base+=i) <= MAX) {
                arr[base] = true;
            }
        }

        for (int i = 2; i < arr.length; i++) {
            if (!arr[i] && !isPalindrome(i)) {
                arr[i] = true;
            }
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if (n == 1) n = 2;
        initPnAndPalindrome();
        for (int i = n; i < arr.length; i++) {
            if (!arr[i]) {
                System.out.println(i);
                return;
            }
        }
    }

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

 

 

 

풀이2

 

  '풀이1'을 돌린 결과값인 'arr'을 확인해보면 사실 소수이면서 팰린드롬인 수가 그리 많지가 않다. 1,003,001까지 확인한 결과 100개정도밖에 안된다. 이러한 경우라면 흔히 하드코딩이라고 불리는 그녀석을 사용할 수 있다 ㅋㅋ

좀 더 이쁘게 말하자면 '런타임 전의 전처리'(precomputation)라고 불린다. 풀이1을 직접 돌리는 것 보다, 돌린 결과를 미리 코드에 써두고 돌리면 당연히 시간복잡도 및 메모리복잡도 모두 이득이다!

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01700/BOJ_1747_precomputation.java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final int[] pnPlaindrome = {2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001};

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < pnPlaindrome.length; i++) {
            if (pnPlaindrome[i] >= n) {
                System.out.println(pnPlaindrome[i]);
                return;
            }
        }
    }

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