백준 1747번 자바

문제

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

1747번: 소수&팰린드롬

 

1. 접근 방식

먼저 소수는 에라토스테네스의 체를 이용해 구해주고

 

팰린드롬수를 어떻게 찾느냐에서 방법이 크게 두가지로 갈린다.

 

첫번째는 많은 블로그에서 기술한 문자 비교방식이다.(투포인터를 활용해 시작과 끝값을 하나씩 비교해준다)

두번째는 내가 사용한 방식인데 10으로 나눈 나머지를 StringBuilder를 활용해 거꾸로 더해주는 방식이다.

 

수의 범위가 큰편이 아니라 10으로 나눠줘도 시간이 크게 오래걸리지 않는다.

다만 숫자의 범위가 더 컸을 경우, 첫번째 방식을 사용하는 것이 시간을 단축하는데 더 유용할 것이다.

 

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main1747 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[1004000];
		for (int i=2; i<arr.length; i++) {
			arr[i] = i;
		}
		// 소수구하기
		for (int i=2; i<Math.sqrt(arr.length); i++) {
			if (arr[i] == 0) {
				continue;
			}
			for (int j=i+i; j<arr.length; j+=i) {
				arr[j] = 0;
			}
		}
		// 가장 작은 펠리드롬 수 구하기
		StringBuilder sb = new StringBuilder();
		for (int i=N; i<arr.length; i++) {
			sb.setLength(0);
			if (arr[i] != 0) {
				int temp = arr[i];
				while (temp != 0) {
					sb.append(temp%10);
					temp /= 10;
				}		
				if (Integer.parseInt(sb.toString()) == arr[i]) {
					System.out.println(sb.toString());
					return;
				} 
			}
		}
	}
}

 

3. 정리

구현 자체는 어렵지 않게 했으나 문제를 잘못 이해해 애를 먹었다. N의 범위가 곧 정답의 범위라고 생각해 생긴 일이었다. N이 최대 1,000,000이 되고 해당 수 보다 큰 펠린드롬수를 구해야하는데 이 부분을 잘못 이해했었다. 항상 문제는 꼼꼼히 읽자..