[백준] 1747번 소수&팰린드롬 자바 java

문제

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

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

 

코드

아무 생각 없이 작성한 코드

입력할 수 있는 범위가 1 ≤ N ≤ 1,000,000 라 소수를 체크하는 과정에서 시간복잡도에 걸린다.

import java.util.Scanner;

public class No1747 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		while(true) {
			if(isPrime(n)&&isPal(Integer.toString(n))) {
				System.out.println(n);
				break;
			}
			n++;
		}
	}
	
	public static boolean isPal(String s) {
		int start=0;
		int end=s.length()-1;
		
		while(start<=end) {
			if(s.charAt(start)!=s.charAt(end))
				return false;
			start++;
			end--;
		}
		
		return true;
		
	}
	
	public static boolean isPrime(int n) {
		boolean isPrime=true;
		for(int i=2;i<n;i++) {
			if(n%i==0)
				isPrime=false;
		}
		
		return isPrime;
	}
}

 

시간복잡도 문제를 해결한 코드

소수를 구할 때 제곱근을 이용하여 구하는 방법을 선택하였다.

우선 소수는 2 이상의 수이므로 입력값이 2보다 작을 때 false를 return 해준다.

 

15를 예로 들자면

1*15, 3*5 (15^(-2)) 5*3, 15*1

 

이런 식으로 제곱근을 기준으로 곱셈의 과정이 대칭이라는 것을 알 수 있다.

 

이 점을 이용해 코드를 작성했다.

(팰린드롬은 숫자를 string으로 전환하여 양쪽 끝을 비교하였다.)

import java.util.Scanner;
//소수&팰린드롬

public class No1747 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		while(true) {
			if(isPrime(n)&&isPal(Integer.toString(n))) {
				System.out.println(n);
				break;
			}
			n++;
		}
	}
	
	public static boolean isPal(String s) {
		int start=0;
		int end=s.length()-1;
		
		while(start<=end) {
			if(s.charAt(start)!=s.charAt(end))
				return false;
			start++;
			end--;
		}
		
		return true;
		
	}
	
	public static boolean isPrime(int n) {
		if(n<2)return false;
		for(int i=2;i*i<=n;i++) {
			if(n%i==0) return false;
		}
		
		return true;
	}
}