[JAVA][Baekjoon] 1747번 소수&팰린드롬 🌟🌟

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

📌 접근 방식

 

1️⃣ 소수 구하기:

• 먼저 1부터 1,000,000까지의 수에 대해 소수를 구했다. 이때 A[i] 배열을 사용하여 A[i] 값이 0이 아니면 소수로 간주하고, 에라토스테네스의 체를 통해 배수들을 지워 소수를 판별했다.

2️⃣ 팰린드롬 판별:

• 소수들을 하나씩 확인하며, 해당 수가 팰린드롬인지를 isPalindrome 메서드를 통해 검사했다. 팰린드롬은 숫자의 순서를 뒤집었을 때 동일한 수가 되면 팰린드롬이기 때문에, 이를 문자열로 변환하여 첫 번째 문자와 마지막 문자를 비교하면서 검사했다.

3️⃣ 최소값 찾기:

• 소수이면서 팰린드롬인 수를 하나씩 찾아가며, 조건을 만족하는 첫 번째 수를 출력하면 되므로, while 루프를 사용해 N부터 시작해서 해당 조건을 만족하는 수를 찾는다.

 

 

✅ PASS CODE

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        // 소수 구하기 - 에라토스테네스의 체
        int []A = new int[10000001];
        for(int i=2; i<A.length; i++){
            A[i] = i;
        }
        for(int i=2; i<Math.sqrt(A.length); i++){
            if(A[i] == 0) continue;
            for(int j=i+i; j<A.length; j+=i) {
                A[j] = 0;
            }
        }
        int i = N;
        while(true) {
            if(A[i] != 0) {
                int result = A[i];
                if(isPalindrome(result)) {
                    System.out.println(result);
                    break;
                }
            }
            i++;
        }
    }
    // 팰린드롬 수 확인
    private static boolean isPalindrome(int x) {
        char tmp[] = String.valueOf(x).toCharArray();
        int s = 0;
        int e = tmp.length - 1;
        while(s < e) {
            if(tmp[s] != tmp[e]) {
                return false;
            }
            s++;
            e--;
        }
        return true;
    }
}

 

😊 느낀 점

이 문제는 소수와 팰린드롬이라는 두 가지 개념을 잘 결합한 문제였다. 특히, 에라토스테네스의 체를 통해 소수를 구하고, 그 중에서 팰린드롬인 수를 찾는 과정이 효율적이었다. 범위가 최대 1,000,000까지 주어지기 때문에 시간 복잡도가 중요한 문제였는데, O(N log log N)의 시간 복잡도를 가진 에라토스테네스의 체로 소수를 구한 후, 팰린드롬 검사는 문자열 비교로 간단히 처리할 수 있어서 효율적이었다.

처음에는 팰린드롬을 어떻게 효율적으로 처리할지 고민했지만, 생각보다 꽤 간단한 문제였다. 그냥 문자의 시작과 끝을 동시에 비교하면서 구하면 된느 거였다!  🧠💡