[코딩테스트] 백준 1747 자바

백준 1747

백준 1747 문제

해당 문제는 에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후 이 소수들의 집합에서 n보다 크거나 같으면서 펠린들모 수인 것을 찾아내면 되는 문제이다.

펠린드롬 수를 판별하기 위해 소수의 값을 char 배열 형태로 변환한 후 양끝의 투 포인터를 비교하면 쉽게 벨린드롬 수인지 판별할 수 있다.

import java.util.*;

public class Boj1747 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 어떤 수
        int[] arr = new int[10000001]; // 소수 배열

        for (int i = 2; i < arr.length; i++) {
            arr[i] = i; // 인덱스를 자기 값으로 소수 배열 초기화
        }

        for (int i = 2; i <= Math.sqrt(arr.length); i++) { // 소수 배열 길이의 제곱근까지 반복
            if (arr[i] == 0) { // 소수가 아니면 넘어감
                continue;
            }

            for (int j = i + i; j < arr.length; j += i) { // 소수의 배수 값을 10000001까지 탐색
                arr[j] = 0; // 소수의 배수는 소수가 아니라는 것을 표시 (배수 지우기)
            }
        }

        int i = n;

        while (true) { // n부터 1씩 증가시키면서 소수와 펠린드롬 수가 맞는지 확인
            if (arr[i] != 0) { // n 이상의 배열 값이 소수이면

                if (isPalindrome(arr[i])) { // 펠린드롬 판별 메서드로 펠린드롬 수인지 확인
                    System.out.println(arr[i]); // 펠린드롬 수이면 출력
                    break; // 반복문 종료
                }
            }
            i++; // 소수 배열 인덱스 증가
        }
    }

    // 펠린드롬 판별 메서드
    private static boolean isPalindrome(int result) {
        char[] temp = String.valueOf(result).toCharArray(); // int값을 char 배열로 변환
        int s = 0; // 시작 인덱스
        int e = temp.length - 1; // 끝 인덱스

        while (s < e) { // 시작 인덱스가 끝 인덱스보다 작을 때까지 반복
            if (temp[s] != temp[e]) { // 만약 시작과 끝 인덱스에 해당하는 값이 다르면
                return  false; // false 반환
            }

            s++; // 시작 인덱스 증가
            e--; // 끝 인덱스 감소
        }

        return true; // 펠린드롬 수이면 true 반환
    }


}

풀이

1. 어떤 수를 입력 받아 n에 저장한다.
2. 10000001 크기의 소수 배열 arr를 선언한다.
3. 2부터 소수 배열의 인덱스를 자기 값으로 초기화한다.
4. 소수 배열 크기의 제곱근까지 반복한다.
   4-1. 소수가 아니면 넘어간다.
   4-2. 소수이면 소수 배열을 탐색하며 소수의 배수는 소수가 아님을 표시한다.(배수 지우기)
5. 무한 루프를 돌며 반복한다.
   5-1. n이상의 배열 값이 소수이면
   5-2. isPalindrome() 메서드로 벨린드롬 수인지 판별한다.
   5-3. 벨린드롬 수이면 출력하고 반복문을 종료한다.
   5-4. 벨린드롬 수가 아니면 n의 값을 증가시키면서 소수이면서 벨린드롬 수인 수를 반복하며 찾는다.
6. isPalindrome() 메서드는 int값을 char 배열 temp로 변환한다.
7. 시작 인덱스 s를 0으로 초기화한다.
8. 끝 인덱스 e를 temp 배열의 길이 -1로 초기화한다.
9. s가 e보다 작으면 반복한다.
   9-1. 시작 인덱스의 값과 끝 인덱스의 값이 다르면 펠린드롬 수가 아니기 때문에 false를 반환한다.
   9-2. 시작 인덱스의 값과 끝 인덱스의 값이 같으면 s는 1 증가, e는 1 감소시켜 시작 인덱스의 값과 끝 인덱스 값이 같은지 확인한다.
   9-3. s가 e보다 작을 때까지 시작 인덱스의 값과 끝 인덱스의 값이 같다면 펠린드롬 수이기 때문에 true를 반환한다.