[Gold 5] [Java] 소수 & 팰린드롬 (1747번)

<소수 & 팰린드롬>

문제 설명

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

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

 

제한 사항

입력

첫째 줄에 N이 주어진다.

 

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

내 생각

우선 N의 범위가 1 ≤ N ≤ 1,000,000로 나와있어서 시간복잡도를 n^2으로 잡을 경우 시간초과가 날 것 같았습니다. 제가 아는 소수를 구하는 방법 중 시간 복잡도가 n^2, n/2, sqrt(n) 이렇게 3가지를 나타낼 수 있는 방법들이 있습니다. 그 중에서 에라토스테네스의 체라는 기법을 사용해 시간복잡도를 sqrt(n)으로 줄이는 방법으로 소수를 찾았습니다. 팰린드롬은 스택을 활용해 뒤집어도 같은지를 판별했습니다. 스택이 숫자크기의 반만큼 스택에 넣고 그 이후의 값들을 비교해 같을경우 스택의 값을 하나씩 제거해줍니다. 스택이 비었을 경우는 뒤집어도 같은 수로 판별되어 팰린드롬이 되고 스택에 값이 있으면 팰린드롬이 되지 않습니다.   

 

걸린 시간

15분 41초

 

작성 코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int answer = 0;
        
        for (int i = n; ; i++) {
            boolean decimal_chk = decimal(i);
            if (decimal_chk) {
                boolean reverse_chk = reverse(i);
                if (reverse_chk) {
                    answer = i;
                    break;
                }
                    
            }
            
        }
        
        System.out.println(answer);
            
    }
 
    public static boolean reverse(int num) {
        boolean flag = false;
        Stack<Character> stack = new Stack<Character>();
        if (1 <= num && num <= 9) {
            flag = true;
            return flag;
        }
        
        String str = num + "";
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (i < str.length()/2) 
                stack.push(ch);
            else {
                if (str.length()%2 != 0 && i == str.length()/2) continue;
                if (stack.peek() == ch) stack.pop();
            }
        }
        
        if (stack.isEmpty()) {
            flag = true;
        }
        
        return flag;
    }
 
    public static boolean decimal(int num) {
        if (num < 2) {
            return false;
        } 
        
        for (int i = 2; i*i <= num; i++) {
            if (num%i == 0) {
                return false;
            }
        }
        
        return true;
    }
 
}
 

 

실행 결과