백준 Java 문제풀이 (62) 1747_소수 & 팰린드롬 수 중에서 최솟값 찾기

 

오늘은 프로젝트로 지친 나의 심신을 달래줄 쉽고 재미있는 문제다.

문제 다 풀고나서 팰린드롬이라는 게 진짜 있는 건지 궁금해서 찾아봤는데

 

 

 

진짜 있구나.. 하도 창의적으로 문제를 지어내는 게 많아서 이번에도 그냥 그런 건 줄 알았다..

 

아무튼 문제를 읽고 조건을 정리해보자

 

 

 

    // 각 자리의 숫자 순서를 뒤집은 수 -> 팰린드롬
    // 79197 <-> 324423
 
    // N보다 크거나 같으면서 소수인 수 중 팰린드롬인 수를 찾을 것.
    // N의 범위 <= 1,000,000 . int로 받을 수 있다.
 
    // 팰린드롬 구하는 방법 유추
    // 1. 1,000,000까지의 소수를 모두 구한다.
    // 2. 입력받은 수를 문자열 배열로 변환하고, 배열의 시작과 끝부터 문자열을 검사한다.
    // 3. 만약 두 문자열이 일치하지 않는 경우 다음으로 넘어간다.
    // 4. 만약 두 포인터가 서로 만나거나 교차하면 팰린드롬 수라고 판단할 수 있다.

 

1. 각 자리의 수를 뒤집어도 같은 수를 팰린드롬이라고 부른다고 한다.

101, 111, 11011 이런 게 다 팰린드롬이다.

 

2. 문제에서 N을 주는데, 이보다 크거나 같은 소수 중 가장 작은 수이면서 팰린드롬인 수를 찾으라고 한다.

 

3. N의 범위는 1,000,000이다. 정수형으로 입력받을 수 있다.

 

4. 그냥 포인터 방식을 활용하면 쉽게 풀 수 있는 문제라고 생각했다.

좌우측 끝부터 하나씩 체크하며 좌우 값이 다르다면 바로 건너뛰고, 결과적으로 값이 같아지거나 교차한다면 그 전까지 계속 값이 같았다는 이야기이기 때문에 팰린드롬일 것이다.

 

 

이를 바탕으로 주석을 작성해보았다.

 
public class Main {
    static int MAX = 1_000_000;
    // 각 자리의 숫자 순서를 뒤집은 수 -> 팰린드롬
    // 79197 <-> 324423
 
    // N보다 크거나 같으면서 소수인 수 중 팰린드롬인 수를 찾을 것.
    // N의 범위 <= 1,000,000 . int로 받을 수 있다.
 
    // 팰린드롬 구하는 방법 유추
    // 1. 1,000,000까지의 소수를 모두 구한다.
    // 2. 입력받은 수를 문자열 배열로 변환하고, 배열의 시작과 끝부터 문자열을 검사한다.
    // 3. 만약 두 문자열이 일치하지 않는 경우 다음으로 넘어간다.
    // 4. 만약 두 포인터가 서로 만나거나 교차하면 팰린드롬 수라고 판단할 수 있다.
    public static void main(String[] args) throws Exception {
        // N 입력받기
 
        // 소수 체크용 boolean 배열
 
        // 에라토스테네스의 체
 
        // 펠린드롬 구하기(소수 배열, N)
 
        // 정답 출력
    }
 
    // 에라토스테네의 체 (소수 체크 배열)
    public static void getPrimeNums(boolean[] arr) {
        // 배열 [0] = 배열 [1] = true
        // 반복문 ( i*i <= 1,000,000 )
            //  if ( 배열[i] = false ) {
                    //    반복문 ( j=i+i; j <= 1,000,000 j+=i ) {
                    //       배열[j] = true;
    }
 
    // 펠린드롬 구하기 (소수 배열, N)
    public static int getPelinedromeNum(boolean[] isNotPrimeNum, int N) {
        // n = N;
 
        // while ( true )
                // String 배열 = String.valueOf(n);
                // l = 0;
                // r = 배열.length()-1;
                //    while ( r >= l && 배열[l].equals(배열[r]) ) {
                    //          if ( r == l ) return n;
                    //    }
                // n++
                // }
    }
}

 

 

음.. 그렇다.

문제를 읽고 너무 쉽다고 생각해버린 나머지 문제 조건을 무시하고 이상하게 주석을 작성했고,

덕분에 이 쉽고 재미있는 문제랑 한참을 씨름했다.

 

평소라면 이 구간에서 조금 더 설명을 하겠지만 위에서 문제 푸는 방법을 거의 완전히 설명해버렸고,

내가 작성한 주석에서 조금만 바꾸면 정답이기 때문에 오늘은 여기서 끝이다

 

다들 행복하십쇼..

정답은 아래에

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
import java.io.*;
 
public class Main {
    static int MAX = 1_000_000;
    // 각 자리의 숫자 순서를 뒤집은 수 -> 팰린드롬
    // 79197 <-> 324423
 
    // N보다 크거나 같으면서 소수인 수 중 팰린드롬인 수를 찾을 것.
    // N의 범위 <= 1,000,000 . int로 받을 수 있다.
 
    // 팰린드롬 구하는 방법 유추
    // 1. 1,000,000까지의 소수를 모두 구한다.
    // 2. 입력받은 수를 문자열 배열로 변환하고, 배열의 시작과 끝부터 문자열을 검사한다.
    // 3. 만약 두 문자열이 일치하지 않는 경우 다음으로 넘어간다.
    // 4. 만약 두 포인터가 서로 만나거나 교차하면 팰린드롬 수라고 판단할 수 있다.
    public static void main(String[] args) throws Exception {
        // N 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        // 소수 체크용 boolean 배열
        boolean[] isNotPrimeNum = new boolean[MAX*2+1];
        // 에라토스테네스의 체
        getPrimeNums(isNotPrimeNum);
 
        // 펠린드롬 구하기(소수 배열, N)
        int answer = getPelinedromeNum(isNotPrimeNum, N);
 
        // 정답 출력
        System.out.println(answer);
    }
 
    // 에라토스테네의 체 (소수 체크 배열)
    public static void getPrimeNums(boolean[] arr) {
        // 배열 [0] = 배열 [1] = true
        arr[0] = arr[1] = true;
        // 반복문 ( i*i <= 1,000,000 )
        for (int i=2; i*i <= arr.length; i++) {
            //  if ( 배열[i] = false ) {
            if (!arr[i]) {
                for (int j=i+i; j < arr.length; j+=i) {
                    //    반복문 ( j=i+i; j <= 1,000,000 j+=i ) {
                    arr[j] = true;
                    //       배열[j] = true;
                }
            }
        }
    }
 
    // 펠린드롬 구하기 (소수 배열, N)
    public static int getPelinedromeNum(boolean[] isNotPrimeNum, int N) {
        // n = N;
        int n = N;
 
        // while ( true ) 0 1 2 3
 
        while (true) {
            if (!isNotPrimeNum[n]) {
                // String 배열 = String.valueOf(n);
                String[] arr = String.valueOf(n).split("");
                // l = 0;
                int l = 0;
                // r = 배열.length()-1;
                int r = arr.length - 1;
                //    while ( r >= l && 배열[l].equals(배열[r]) ) {
                while (r >= l && arr[l].equals(arr[r])) {
                    //          if ( r == l ) return n;
                    //    }
                    l++;
                    r--;
                    if (r <= l) return n;
                }
                // n++
                // }
            }
            n++;
        }
    }
 

 

 

위 주석이 틀린 이유

 

1. n보다 크거나 같은 수 중에라고 했는데, 바보 같이 최대 값을 1000000으로 잡음.

2. 자리 판단하는 위치가 미묘하게 잘못됨.