Bj_1747
title: 2025-08-15 author: 강병호 date: 2025-08-15 (날짜) category: TIL/강병호/2025/08 (파일 경로 : TIL/{이름}/{연}/{월}) layout: post (자유) —
1차 제출
- 에라토스테네스의 체를 이용해서 boolean 배열 처리
- 팰린드롬 함수를 사용하여 확인 (숫자를 String화 시킨 후 확인) ``` // 소수 + 팰린드롬 구하기 // N 보다 크거나 같은 수
import java.util.Arrays; import java.util.Scanner;
public class Main {
static final int lastNum = 1000000;
static boolean[] nums = new boolean[lastNum + 1];
private static void eratos() {
Arrays.fill(nums, true);
nums[0] = false;
nums[1] = false;
for (int i = 2; (i*i) <= lastNum; i++) {
if (nums[i]) { // 소수이면
for (int j = i*i; j <= lastNum; j += i) {
// 배수들 모두 false 처리
nums[j] = false;
}
}
}
}
private static boolean checkPalindrome(String num) {
int length = num.length();
for (int i = 0; i < length / 2; i++) { // 0 1 2 3 4
if (num.charAt(i) != num.charAt(length- i - 1)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
eratos();
for (int i = N; i < lastNum; i++) {
if (nums[i]) {
if (checkPalindrome(Integer.toString(i))) {
System.out.println(i);
break;
}
}
}
}
} ```
해당하는 로직이 1%도 되지 않고 실패…
해당 이유는 문제에 있다.
문제 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.
여기서 입력이 1000000까지 인 것이지 팰린드롬 수는 해당 수보다 더 커질 수 있음.
이를 고려해서 new boolean[1000000] -> new boolean[2000000] 으로 변경하여 성공.
ps. 좀 더 메모리 효율을 위해 1000000번째 수 확인해서 줄여도 될 듯…