[Java] BOJ1747, 백준 - 소수&팰린드롬

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

1747번: 소수&팰린드롬

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256MB	10512	3115	2271	28.387%

문제

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

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

 

입력

첫째 줄에 N이 주어진다.

 

출력

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

 

<풀이>

1. 가장 먼저 범위 내의 소수를 구한다.
   • N이 1,000,000까지인데, 1,000,000보다 크거나 같은 소수이고 팰린드롬인 수는 1,003,001이기 때문에 이 숫자까지의 소수를 미리 구해놓는다.
2. N부터 시작해서 N이 소수라면, 팰린드롬인지 검사한다.

* 한 가지 주의사항: 1은 소수가 아니다

 

시간복잡도

에라토스테네스의 체의 시간복잡도 : O(Nlog(logN))

N=1,003,001일 때, 약 78만

 

팰린드롬인지 검사하는 알고리즘: 숫자의 길이/2인데, 최대 숫자의 길이가 7이기 때문에 무시해도 되는 수준

(1,003,001까지의 모든 수의 팰린드롬을 검사한다고 하더라도 시간 내에 해결가능)

 

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		// 소수인지 아닌지 저장할 배열
		boolean[] prime = new boolean[1003002];

		// 1은 소수가 아니다
		prime[1] = true;

		// 에라토스테네스의 체
		for (int i = 2; i < prime.length; i++) {
			if (!prime[i])
				for (int j = i + i; j < prime.length; j += i)
					prime[j] = true;
		}

		// 소수이고(prime[n]=false), 팰린드롬인(palindrome(n)=true)를 동시에 만족하는
		// n을 찾을때까지 반복
		while (prime[n] || !palindrome(n))
			n++;

		System.out.println(n);
	}

	// 팰린드롬 검사
	private static boolean palindrome(int n) {
		String s = String.valueOf(n);

		for (int i = 0; i < s.length() / 2; i++)
			if (s.charAt(i) != s.charAt(s.length() - i - 1))
				return false;

		return true;
	}
}