백준저지 1747번 소수&팰린드롬

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

1747번: 소수&팰린드롬

 

 

접근 방법

숫자를 입력 받고 2부터 시작해서 반복문을 사용해서 구현한 에라토스테네스의 해를 통해 소수인지 확인한다. 소수가 맞다면 주어진 수보다 큰 경우(https://www.acmicpc.net/board/view/12646)에 팰린드롬인지 확인한다.

int형 배열을 1003002 크기만큼 만드는데, 이유는 N의 최댓값인 1000000일 때 최대로 나올 수 있는 답이 1003001이기 때문(https://www.acmicpc.net/board/view/27380)이다. 

 

 

 

생각

에라토스테네스의 해를 예전에는 int형 배열을 사용해서 풀었는데 이번에는 boolean으로 풀어봤다.

문제를 풀 때 시간이 생각보다 많이 걸렸는데, 우선 for문 위치를 if문 밖에 넣어서 틀렸고, 이후에는 k=i*j 처리를 안해서 틀렸었다. 반복문 안에 변수 여러 개를 넣다보니 헷갈렸다. 그래서 다른 문제 풀 때 그냥 변수를 따로 선언했는데 그게 나한테는 더 직관적인 것 같다.

 

 

 

코드

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

public class BOJ1747 {

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

    private static void getPrimePalindrome(int n) { // 에라토스테네스의 체
        boolean[] isPrime = new boolean[1003002]; // 입력값 N이 최댓값인 1000000일 때의 답은 1003001
        Arrays.fill(isPrime, true); // 우선 소수라고 가정 (true)
        for (int i = 2; i < 1003002; i++) { // 2부터 소수인지 확인
            if (isPrime[i]) { // 소수라면
                if (i >= n && isPalindrome(i)) { // 주어진 N보다 크고 펠린드롬일 경우 답 출력하고 끝
                    System.out.println(i);
                    break;
                }
                for (int j = 2, k = i * j; k < 1003002; j++, k = i * j) {
                    isPrime[k] = false; // 소수는 false로 체크
                }
            }
        }
    }

    private static boolean isPalindrome(int n) { // 팰린드롬 
        String str = String.valueOf(n);
        for (int i = 0; i < str.length() / 2; i++) {
            if (str.charAt(i) != str.charAt(str.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }

}