백준 1747. 소수&팰린드롬 (브루트포스, 소수, 팰린드롬)

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

문제제목 : 소수&팰린드롬

문제난이도 : 골드5

문제유형 : 브루트포스

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

---

코드1의 접근방식

1. 펠린드롬인 수를 찾는다. 팰린드롬은 스택을 이용하여 확인한다.

2. 그 수가 소수인지 확인한다.

3. 소수면 출력하고 아니면 +1을 하여 반복한다.

코드1. (시간복잡도 772ms) - 느리다! 

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Character> stack = new Stack<>();
		
		int N = sc.nextInt();
		
		String number = String.valueOf(N);
		while (true) {
			//System.out.println(number + "====시작");
			// 스택 삽입
			for (int i = 0; i < number.length(); i++) {
				stack.push(number.charAt(i));
			}
			
			
			// 팰린드롬 인 수 찾기
			boolean isp = true;
			for (int i = 0; i < number.length(); i++) {
				if (!stack.isEmpty() && stack.pop() != number.charAt(i)) {
					isp = false;
					break;
				}
			}
			
			
			if (isp) {
				//System.out.println(number + "가 펠렘");
				boolean isPrime = true;
				//팰린드롬을 찾았다면 소수판별
				int a = Integer.parseInt(number);
				if (a == 1) {
					isPrime = false;
					number = String.valueOf(Integer.parseInt(number) + 1);
				}
				for (int i = 2; i < a; i++) {
					if (a % i == 0) {
						isPrime = false;
						number = String.valueOf(Integer.parseInt(number) + 1);
						break;
					}
				}
				if (isPrime) {
					System.out.println(a);
					break;
				}
			} else {
				// 팰린드롬이 아니라면 +1
				number = String.valueOf(Integer.parseInt(number) + 1);
			}
		}
		
	}

---

코드2의 접근방식

1. 소수를 찾는다.

2. 소수가 팰린드롬인지 확인한다.

3. 맞으면 출력하고 아니면 +1을 하여 반복한다.

코드2. (시간복잡도 572ms) - 아직 느리다. 소수판별도 에라토스테네스의 체를 이용하여 시간을 더 줄이는 것이 효율적이다.

import java.util.Scanner;

public class BOJ1747 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int number = N;
		while(true) {
			if (fine_prime(number)) {
				if (palindrome(number)) {
					System.out.println(number);
					break;
				}
			}
			number++;
		}
	}
	
	public static boolean fine_prime(int num) {
		if (num < 2) {
			return false;
		}
		
		for (int i = 2; i * i <= num; i++) {
			if (num % i == 0) {
				return false;
			}
		}
		return true;
	}
	
	public static boolean palindrome(int num) {
		String n = String.valueOf(num);
	
		for (int i = 0; i < n.length() / 2; i++) {
			if (n.charAt(i) != n.charAt(n.length() - 1 - i)) {
				return false;
			}
		}
		return true;
	}
	
}

---

코드3의 접근방식

1. 에라토스테네스의 체를 이용하여 소수를 찾는다.

2. 소수가 팰린드롬인지 확인한다.

3. 맞으면 출력하고 아니면 +1을 하여 반복한다.

코드3. (시간복잡도 300ms)

package week6;

import java.util.Scanner;

public class BOJ1747 {

	public static boolean[] prime = new boolean[2000000];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//0,1은 소수가 아님.
		for (int i = 2; i < prime.length; i++) {
			prime[i] = true;
		}
		
		//소수 아닌 수 판별: 제곱근까지 해당하는 범위안의 소수의 배수를 제외하면 됨. (에라토스테네스의 체)
		for (int i = 2; i * i < prime.length; i++) {
			if (prime[i]) {
				for (int j = i * 2; j < prime.length; j += i) {
					prime[j] = false;
				}
			}
		}
		
		int N = sc.nextInt();
		
		int number = N;
		while(true) {
			if (prime[number]) {
				if (palindrome(number)) {
					System.out.println(number);
					break;
				}
			}
			number++;
		}
	}
	
	public static boolean palindrome(int num) {
		String n = String.valueOf(num);
	
		for (int i = 0; i < n.length() / 2; i++) {
			if (n.charAt(i) != n.charAt(n.length() - 1 - i)) {
				return false;
			}
		}
		return true;
	}
}

제곱근까지 해당하는 범위안의 소수의 배수를 제외하면 된다. (에라토스테네스의 체)

만약 N=100일 경우, 100까지의 소수를 판별하고 싶다면, 2부터 100의 제곱근인 10까지에 대한 소수의 배수를 제외하면 된다.