[백준_1747번] 소수&팰린드롬

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

1747번: 소수&팰린드롬

[문제]

 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

 

[입력 조건]

첫째 줄에 N이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_1747 {
	static boolean[] Prime=new boolean[1000001];
	static int n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		// n이 1일 경우 예외처리!
		if(n==1) {
			System.out.println(2);
			System.exit(0);
		}
		
		// n보다 큰 수 중 소수이면서 팰린드롬을 만족하는 수 찾기
		for(int i=n;;i++) {
			if(isPrime(i)&&isPalind(i)) {
				System.out.println(i);
				System.exit(0);
			}
		}	
	}
	
	// n이 소수인지 판별하는 함수 -> 에라토스테네스의 채 알고리즘
	static boolean isPrime(int num) {
		for(int i=2;i<=Math.sqrt(num);i++)
			if(num%i==0)
				return false;
		
		return true;
	}
	
	// n이 팰린드롬 수 인지 판별하는 함수
	static boolean isPalind(int num) {
		String str=Integer.toString(num);
		int len=str.length();
		
		for(int i=0;i<=len/2;i++) {
			if(str.charAt(i)!=str.charAt(len-1-i))
				return false;
		}
		
		return true;
	}
}

 

[고찰]

 이번 문제는 소수를 찾는 문제와 팰린드롬을 찾는 문제가 합쳐진 문제였다. 소수를 구하는 것은 에라토스테네스의 채 알고리즘을 여러 문제들을 통해 풀어봤기 때문에 쉽게 해결할 수 있었고 팰린드롬 수를 구하는 것도 어렵지 않았다. 수의 대칭되는 인덱스의 숫자가 같은지 비교하는 방식으로 해결할 수 있었다. 이렇게만 풀었을 때는 오답 처리를 받았는데 그 이유는 n이 1일 때의 예외처리를 해주지 않았기 때문이다. 이 부분도 작성해주어야 정답 처리를 받을 수 있다.