[백준 자바 1747] 소수&팰린드롬 (실버 1)

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

1747번: 소수&팰린드롬

 

코드 전체는 맨 아래에 있습니다! 

 

풀이

 

문제의 조건은 다음과 같다. 

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

 

처음에는 소수이니까 에라토스테네스의 체를 쓸 생각이었다. 

근데 문제 조건이 N보다 크거나 같다고 쓰여있어서, 머리 동동 굴렸다. 정수 최대값인 21억 길이의 배열을 만들어서 소수를 다 구해놓고 하려다가, 혹시나 21억이 넘겨버리면 문제 틀릴텐데, 등등 생각만 하다가 같이 공부하는 분이 소수판별 알고리즘 써보라고 힌트를 주셨다. 

(아래도 썼지만, 100만 이상인 값이면서 소수&팰린드롬인 값이 21억을 넘길리가 없었다.)

 

지금까지 소수 == 에라토스테네스의 체 여서 생각 못하고 있었다.. O(N^(1/2)) 로 구하는 방법도 있었다. 

static boolean isPrimeNumber(int num) {
    if (num < 2) {
        return false;
    }

    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

 

맨 처음의 2보다 작은 값을 판단하는 if문을 안 넣었더니 입력 1에 출력 1이 나와서 99%에서 틀렸다. 이런 엣지 케이스도 잘 고려해야 하는데 아직 갈 길이 멀다.. 

 

그 다음 팰린드롬은 문자열의 절반을 나눠서 양측을 점점 좁혀가며 비교하면 되는 간단한 구현이다. 

static boolean isPalindrome(int num) {
    char[] chars = String.valueOf(num).toCharArray();
    for (int i = 0; i < chars.length / 2; i++) {
        if (chars[i] != chars[chars.length - i - 1]) {
            return false;
        }
    }
    return true;
}

먼저 숫자를 문자의 배열로 변환한 뒤, 길이의 절반만 for문을 돌린다. 

이때 홀수는 가운데값이 어느 값이어도 상관없어서 비교하지 않아도 되는데, 길이의 절반을 나누면 무시가 된다. 

만약 좌우 값이 다르면 팰린드롬이 아니므로 조기 false 리턴을 하고, 다 돌았다면 true 리턴을 해준다. 

 

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    while (true) {
        if (isPalindrome(n) && isPrimeNumber(n)) {
            System.out.println(n);
            return;
        }
        n++;
    }
}

이후 문제의 조건에 따라, n 이상의 최솟값을 구해야 하니 n을 점점 올려가며 팰린드롬인지와 소수인지를 체크하고, 조건을 처음으로 만족하는 값(값을 올려가므로 최솟값) 을 출력 후 종료한다. 

 

문제에서 상한을 알려주지 않아서 while (true)를 쓰면서 걱정?을 했었긴 한데, 다시 생각해보면 100만 이상인 값 중에 최솟값이라 당연히 21억 안에 하나쯤은 나오겠긴 했겠네 

 

 

 

---

 

전체 코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while (true) {
            if (isPalindrome(n) && isPrimeNumber(n)) {
                System.out.println(n);
                return;
            }
            n++;
        }
    }

    static boolean isPrimeNumber(int num) {
        if (num < 2) {
            return false;
        }

        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    static boolean isPalindrome(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        for (int i = 0; i < chars.length / 2; i++) {
            if (chars[i] != chars[chars.length - i - 1]) {
                return false;
            }
        }
        return true;
    }
}