[백준] 1747 소수 & 펠린드롬 java 풀이

1. 문제 설명 📌

문제 링크

2. 구현 방법 🗃️

KEY WORD: 에라토스테네스의 체, 문자열

• 1️⃣ N의 최대값의 2배에 해당하는 부분에 대하여 소수 전부 찾아놓기 (N의 최대값: 1,000,000이라 가능)
• 2️⃣ 입력 받기
• 3️⃣ 입력보다 크거나 같은 값 중 펠린드롬 (뒤집어도 같은 수)인지 확인하기.

(1) 시간복잡도 분석 🕓

임의의 수: $N$ (최대값: 1,000,000)

• 에라토스테네의 체 만들기: $O(2N \log (\log 2N))$
• 펠린드롬 수 찾기: input에서 제일 가까운 소수 이자 펠린드롬 수를 찾는 것이므로, 시간 복잡도 따로 계산하지 않아도 될 만큼 작은 반복안에 찾음.

3. 코드 소개 🔎

(1) SUDO CODE

• 0️⃣ 1에서 2,000,000까지의 영역에서 소수 전부 찾아놓기
• 1️⃣ input 받기
• 2️⃣ input보다 크거나 같은 소수 찾기
• 3️⃣ 해당 소수가 펠린드롬 수인지 확인 (아니면 2️⃣ 계속 해 나감, 맞으면 2️⃣ 탈출)

(2) JAVA CODE

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


public class Main {
    static StringBuilder straight, reverse;
    static boolean [] isPrime = new boolean[2_000_001]; // true = 소수, false = 소수 아닌 수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());
        prime_shifter();
        System.out.println(find_first_palindrome(input));
    }

    private static void prime_shifter(){
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        double root_max = Math.sqrt(2_000_000);
        for (int i = 2; i < root_max; i++) {
            if(isPrime[i]) {
                for (int j = i*i; j <= 2_000_000; j+=i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    private static int find_first_palindrome(int input){
        for (int i = input; i < 2_000_001; i++) {
            if (!isPrime[i]) continue;
            if (is_palindrome(i)) return i;
        }
        return -1;
    }

    private static boolean is_palindrome(int num){
        straight    = new StringBuilder(Integer.toString(num));
        reverse     = new StringBuilder(Integer.toString(num)).reverse();
        boolean ans = straight.toString().equals(reverse.toString());
        straight.setLength(0);
        reverse.setLength(0);
        return ans;
    }
}

4. 배운 것들 🎯

(1) StringBuilder를 활용해 문자열을 뒤집을 때, 주의사항 ⚠️

처음엔 다음 코드와 같이 StringBuilder()의 생성자에 숫자를 문자열로 변환하지 않고 값을 집어넣었다.

    private static boolean is_palindrome(int num){
        straight    = new StringBuilder(num);
        reverse     = new StringBuilder(num).reverse();
        boolean ans = straight.toString().equals(reverse.toString());
        straight.setLength(0);
        reverse.setLength(0);
        return ans;
    }

이렇게 넣어도 숫자가 문자열 형태로 StringBuilder에 들어갈 줄 알았으나, 내 착각이었다. StringBuilder의 생성자는 int 형 넣었을 때와 문자열을 넣었을 때가 다르다!

String 넣었을 시,

@IntrinsicCandidate
    public StringBuilder(String str) {
        super(str);
    }

우리가 아는 내용물로 문자열을 집어 넣는다.

int형 넣었을 시,

    @IntrinsicCandidate
    public StringBuilder(int capacity) {
        super(capacity);
    }

StringBuilder의 수용량 즉 StringBuilder 내부 버퍼의 초기 크기를 결정하는 생성자에 값이 들어간다. 따라서 매개변수가 StringBuilder의 내용물로 들어가지 않는다.