[백준] 1990번 : 소수인팰린드롬 – JAVA [자바]

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

 

 

 

---

문제

 

 

---

해결 방법

이 문제는 소수 판별 및 팰린드롬 검사를 활용한 수 필터링 문제이다. 다음과 같은 방식으로 해결할 수 있다.

1. B까지의 소수를 구한다.
에라토스테네스의 체를 이용하여 B 이하의 모든 소수를 구한다.
BitSet을 사용하여 불필요한 메모리 사용을 줄이고 빠르게 소수를 판별한다.

 

여기서 BitSet이란 비트 단위로 값을 저장하는 자바의 자료구조이다.
즉, 1개의 비트(0 또는 1)만 사용하여 데이터를 관리할 수 있다.

 

Boolean 값(true/false)을 비트 단위로 저장하므로, 메모리를 크게 절약할 수 있다.

 

자바에서 boolean []을 사용하면, 각 boolean 값이 1 byte (8 bits)를 차지한다.
하지만 BitSet은 한 개의 boolean을 1 bit 만 사용하므로 메모리를 8배 절약할 수 있다.

자료구조	저장 단위	100,000,000개의 값 저장 시 메모리
boolean[]	1개당 8 bits (1 byte)	100MB (100,000,000 bytes)
BitSet	1개당 1 bit	12.5MB (100,000,000 bits ÷ 8)

즉, boolean []보다 BitSet을 사용하면 메모리를 1/8로 줄일 수 있다.

2. 소수 중에서 팰린드롬 수를 찾는다.
소수 리스트를 순회하며 각 숫자가 팰린드롬인지 확인한다.
팰린드롬은 숫자를 뒤집었을 때 원래 값과 동일한 경우를 의미한다.

3. 결과 출력
A 이상 B 이하의 숫자 중에서 소수이면서 팰린드롬인 수를 출력한다.
마지막 줄에 -1을 출력하여 종료를 알린다.

 

 

---

코드 

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        StringBuilder sb = getPrimePalindromes(a, b);
        sb.append("-1");
        System.out.print(sb);
    }

    // 주어진 범위에서 소수인 팰린드롬 찾기
    public static StringBuilder getPrimePalindromes(int min, int max) {
        StringBuilder sb = new StringBuilder();
        BitSet bitSet = new BitSet(max + 1);
        bitSet.set(2, max + 1); // 2부터 max까지 모든 숫자를 기본적으로 소수로 설정

        // 에라토스테네스의 체 적용
        for (int i = 2; i * i <= max; i++) {
            if (bitSet.get(i)) {
                for (int j = i * i; j <= max; j += i) {
                    bitSet.clear(j); // 소수가 아닌 수 제거
                }
            }
        }

        // 주어진 범위에서 소수이면서 팰린드롬인지 검사
        for (int i = min; i <= max; i++) {
            if (bitSet.get(i) && isPalindrome(i)) {
                sb.append(i).append("\n");
            }
        }
        return sb;
    }

    // 숫자가 팰린드롬인지 판별
    public static boolean isPalindrome(int n) {
        int original = n;
        int reverse = 0;
        while (n > 0) {
            reverse = reverse * 10 + (n % 10);
            n /= 10;
        }
        return original == reverse;
    }
}

 

 

---

코드 설명

1. 소수 판별 (getPrimePalindromes)
BitSet을 사용하여 메모리 절약
에라토스테네스의 체 알고리즘을 사용해 빠르게 소수를 구함
min부터 max까지 반복하면서 소수 & 팰린드롬 여부 확인

 

2. 팰린드롬 판별 (isPalindrome)
숫자를 뒤집어 원본과 비교 (O(log N))
문자열 변환 없이 연산으로 해서 속도를 최적화시킨다 (문자열로 변환해서 비교하면 더 느리다)

 

그리고 에라토스테네스의 체를 왜 j = i * 2부터 안 하고 j = i * i부터 하는지 설명하겠다.

// 에라토스테네스의 체 적용
        for (int i = 2; i * i <= max; i++) {
            if (bitSet.get(i)) {
                for (int j = i * i; j <= max; j += i) {
                    bitSet.clear(j); // 소수가 아닌 수 제거
                }
            }
        }

 

 

1. 기본 개념: 에라토스테네스의 체

에라토스테네스의 체를 사용하면 소수의 배수를 제거해서 소수를 빠르게 구할 수 있다. 예를 들어, i가 소수라면 i의 배수는 모두 소수가 아니므로 제거해야 한다.

 

일반적인 방식

for (int j = i * 2; j <= max; j += i) {
    isPrime.clear(j);
}

 

이 방식은 정확히 작동하지만, 불필요한 연산이 많다.

예를 들어 i = 5라면 j = 5 * 2 = 10부터 시작해서 j += 5로 증가하면서 모든 배수를 지운다. 하지만 10은 이미 i = 2 또는 i = 3에서 지워졌을 가능성이 높아서 할 필요는 없다.

 

2. 더 최적화된 방식 (int j = i * i)

for (int j = i * i; j <= max; j += i) {
    isPrime.clear(j);
}

 

이 방식이 더 효율적인 이유는:
1. i보다 작은 배수는 이미 제거됨:
예를 들어 i = 5라면, 5 * 2 = 10, 5 * 3 = 15 같은 수는 이미 2나 3에서 처리되었으므로 굳이 또 지울 필요가 없다.

 

2. 최소한의 반복으로 배수 제거 가능:
예를 들어 i = 7일 때, j = 7 * 7 = 49부터 시작한다.
j = 14, 21, 28, 35, 42 같은 작은 배수는 이미 2나 3에서 지워졌다.
즉, j = i * i부터 시작하면 불필요한 연산을 줄일 수 있어서 더 효율적이다.

 

 

---

시간 복잡도 분석

1. 소수 판별 (에라토스테네스의 체)

에라토스테네스의 체의 시간 복잡도는: O(N log (log N)) → N ≈ 100,000,000 일 때도 빠르게 실행 가능

 

2. 팰린드롬 판별 (O(log N))
최대 100,000,000 → 자릿수는 ≤ 8 → 매우 빠름

 

3. 총 복잡도
O(N log (log N)) + O(N log N) ≈ O(N log (log N))