백준 1990번: 소수인팰린드롬 (JAVA)

문제

151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오.

입력

입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a < b ≤ 100,000,000 이다.

출력

첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다.

 

---

 

풀이

1. b까지 소수를 에라토스테네스 체를 이용하여 구한 후, 소수에 대하여 팰린드롬인지 확인한다. 
2. 1. 개선: '자리수가 짝수이면서 팰린드롬이면 소수가 아니다'는 관찰을 이용, b가 천만이 넘으면 천만까지만 소수를 구한다.
   • 증명: n이 홀수일 때 10^n = 1(mod 11), n이 짝수일 때 10^n = -1(mod 11)이다. 그리고 abba와 같은 숫자에서 두 a의 위치를 생각해보면, 하나는 홀수번째 자리, 하나는 짝수번째 자리에 있다. 따라서 1000a + a = (-1)*a + a = 0 (mod 11).

 

배운 점

팰린드롬 구하는 문제를 Python에서 문자열 reverse해서 같은지로만 해서 순간 구하는 방법을 까먹었다. 당황하지 말고, 숫자일때는 10으로 나눈 나머지를 더하고 10씩 곱해나가면서 숫자를 만들어서 같은지 확인하자.

코딩테스트랑은 크게 상관없겠지만, 아이디어가 있으면 확실히 이득을 볼 수 있는 점이 있다.

 

코드

풀이 1. 그냥 에라토스테네스

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		StringBuilder sb = new StringBuilder();
		boolean[] notPrimeCandidate = new boolean[b+1]; // 초기값 false가 소수인 상태로 저장하기 위함: 시간 절약
		
		for (int i = 2; i*i < b+1; i++) {
			if (!notPrimeCandidate[i]) {
				notPrimeCandidate[i] = false;
				for (int j = 2*i; j < b+1; j += i) {
					notPrimeCandidate[j] = true;
				}
			}
		}
		
		for (int i = a; i <= b; i++) {
			if (!notPrimeCandidate[i] && isPalindrome(i)) {
				sb.append(i+"\n");
			}
		}
		sb.append(-1);
		System.out.println(sb);
	}
	
	
	static boolean isPalindrome(int n) {
		int temp = n;
		int reverse = 0;
		while (temp > 0) {
			reverse *= 10;
			reverse += temp % 10;
			temp /= 10;
		}
		return n == reverse;
	}

}

 

풀이 2. 에라토스테네스 체, 천만 이하로 범위 제한

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		b = Math.min(10000000, b); // 천만 이상 1억 이하에는 펠린드롬 소수가 없음, 1억은 펠린드롬 소수가 아님.
		
		StringBuilder sb = new StringBuilder();
		boolean[] notPrimeCandidate = new boolean[b+1]; // 초기값 false가 소수인 상태로 저장하기 위함: 시간 절약
		
		for (int i = 2; i*i < b+1; i++) {
			if (!notPrimeCandidate[i]) {
				notPrimeCandidate[i] = false;
				for (int j = 2*i; j < b+1; j += i) {
					notPrimeCandidate[j] = true;
				}
			}
		}
		
		// 수의 길이가 짝수이면서 펠린드롬이면 11의 배수이다.
		for (int i = a; i <= b; i++) {
			if (i == 1000) i = 10001;
			if (i == 100000) i = 1000001;
			if (!notPrimeCandidate[i] && isPalindrome(i)) {
				sb.append(i+"\n");
			}
		}
		sb.append(-1);
		System.out.println(sb);
	}
	
	// 팰린드롬 확인
	static boolean isPalindrome(int n) {
		int temp = n;
		int reverse = 0;
		while (temp > 0) {
			reverse *= 10;
			reverse += temp % 10;
			temp /= 10;
		}
		return n == reverse;
	}

}

 

퍼포먼스 비교

풀이 1은 1536ms, 풀이 2는 244ms가 걸렸다. 메모리 사용에서도 확실히 낫다.

(참고로 144ms 걸린 풀이는 결과값 배열로 저장해서 출력한 것이니 신경쓰지 않아도 된다 ㅎㅎ;;)