백준 1747 소수&팰린드롬

문제

풀이

import java.util.*;

public class Q1747_소수와팰린드롬 {

    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;
        }
		
		// 2부터 1씩 증가하며 소수를 판별
        // n = a * b라고 했을 때 a와 b 모두 n의 제곱근보다 클 수 없으므로
        for (int i = 2; i < Math.sqrt(arr.length); i++) {
            if (arr[i] != 0) {
                // 각 j의 배수는 소수가 될 수 없으므로
        		// 0으로 치환
                for (int j = i + i; j < arr.length; j += i) {
                    arr[j] = 0;
                }
            }
        }
        int result = 0;
        
        // n부터 1씩 증가할 인덱스 변수
        int idx = n;
        while (true) {
            if (arr[idx] != 0) {
            	// arr[idx]의 값을 char형 배열로 변환
                char[] tmp = String.valueOf(arr[idx]).toCharArray();
                int s = 0;
                int e = tmp.length - 1;
                
                // 필렌드롬인지 확인하기 위한 변수
                boolean check = true;
                
                // 시작 인덱스와 끝 인덱스를 서로 비교해 감
                while (s < e) {
                	// 만약 일치하지 않는 숫자가 나오면 반복문을 빠져나옴
                    if (tmp[s] != tmp[e]) {
                        check = false;
                        break;
                    }
                    s++;
                    e--;
                }
                
                // 만약 check변수가 true라면 해당 숫자는 필랜드롬이라는 뜻이므로
                // 결과를 result변수에 저장하고 반복문을 빠져나옴
                if (check) {
                    result = idx;
                    break;
                }
            }
            idx++;
        }
        // 결과를 출력
        System.out.println(result);
    }
}

리뷰

문제를 해결하기 위한 아이디어 자체는 그다지 어렵지 않았다.

1. 에라토스테네스의 체를 이용하여 소수를 구하고
2. 이 숫자가 팰린드롬인지 확인한다.
   • 먼저 숫자를 String값으로 변경하고,
     .toCharArray()메서드를 이용해 char형 배열로 변형시킨다.
   • 그 후 시작 인덱스는 1씩 증가하고, 끝 인덱스는 1씩 감소시키며
     두 인덱스에 들어있는 문자가 일치하는지 확인해주면 된다.

문제 자체는 몇분 걸리지 않았는데, 2가지 문제로 인해 시간이 오래걸렸다ㅜㅜ

1. 배열의 크기 설정
   처음에 나는 단순히 1 ≤ N ≤ 1,000,000의 범위이기 때문에 배열을 1,000,001로 설정하면 되는 줄 알았다.
   그런데 실제 풀이를 보니 이보다 *10만큼 큰 10,000,001로 설정한 것을 알 수 있었다. 그 이유는 다음과 같다.

• 소수 체 알고리즘은 각 숫자의 배수를 제거하며 소수를 판별하는데, 이 과정에서 배열의 크기가 충분히 크지 않으면 주어진 범위를 벗어나는 인덱스에 접근하려고 할 수 있다. 따라서 배열의 크기를 최대 범위보다 크게 설정하여 이러한 오류를 방지하는 것이 중요하다고 한다.

2. 1을 소수로 포함시킴
   주어진 N의 크기는 1 ≤ N ≤ 1,000,000이다. 따라서 n으로 1이 주어질 수가 있는데 1은 소수는 아니지만 펠린드롬이라고 할 수 있다.
   그런데 나는 이걸 고려하지 못하고 배열 초기화 부분과 소수 판별 반복문을 아래와 같이 설정을 해버렸다.

        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

		for (int i = 2; i < Math.sqrt(arr.length); i++) {
            if (arr[i] != 0) {
                for (int j = i + i; j < arr.length; j += i) {
                    arr[j] = 0;
                }
            }
        }

이렇게 설정을 해버리니 소수가 아닌 1은 배열에 그대로 1로 남아있게 됐다.

문제를 푼줄 알고 잠깐 뿌듯했는데 계속 틀렸다고 떠서 스트레스 받다가 뭐가 문제였는지 확인하니 속이 시원하면서도 허무했다ㅜㅜ