자바 코딩테스트 강좌, 소수 & 팰린드롬 수 중에서 최솟값 찾기

문제 정의

주어진 범위 내에서 소수이면서 팰린드롬인 수들 중에서 최솟값을 찾는 문제입니다. 소수는 1과 자기 자신만을 약수로 갖는 자연수를 의미하며, 팰린드롬은 앞뒤가 똑같은 수를 의미합니다. 예를 들어, 121은 팰린드롬 수이고 131, 151, 181, 191도 소수이며 팰린드롬입니다.

문제 접근 방법

이 문제를 해결하기 위해 다음과 같은 단계를 거칠 것입니다:

  1. 주어진 범위 내에서 소수를 찾는 방법을 구현합니다.
  2. 찾은 소수들 중에서 팰린드롬 수를 확인하는 방법을 구현합니다.
  3. 팰린드롬인 소수들 중에서 최솟값을 찾습니다.

1단계: 소수를 찾는 함수 구현

소수를 찾기 위해 간단한 소수 판별 알고리즘을 사용할 수 있습니다. 이 알고리즘은 어떤 숫자가 다른 숫자들로 나누어 떨어지지 않는지 확인함으로써 소수를 판별합니다. 아래는 Java로 구현한 소수 판별 코드입니다.

public class PrimeUtil {
        public static boolean isPrime(int number) {
            if (number <= 1) return false;
            for (int i = 2; i <= Math.sqrt(number); i++) {
                if (number % i == 0) return false;
            }
            return true;
        }
    }

2단계: 팰린드롬 확인 함수 구현

팰린드롬 수를 확인하기 위해 문자열로 변환하고, 원래 문자열과 반전 문자열이 같은지를 비교하는 방법을 사용할 수 있습니다. 이를 Java로 구현한 코드는 다음과 같습니다.

public class PalindromeUtil {
        public static boolean isPalindrome(int number) {
            String str = Integer.toString(number);
            String reversedStr = new StringBuilder(str).reverse().toString();
            return str.equals(reversedStr);
        }
    }

3단계: 최솟값 찾기

소수이면서 팰린드롬인 수들을 찾은 후, 이들 중에서 최솟값을 찾는 코드를 작성합니다. 이 부분의 코드 또한 Java로 구현하도록 하겠습니다.

import java.util.ArrayList;
    import java.util.List;

    public class MinPrimePalindromeFinder {
        public static int findMinPrimePalindrome(int start, int end) {
            List<Integer> primePalindromes = new ArrayList<>();
            for (int i = start; i <= end; i++) {
                if (PrimeUtil.isPrime(i) && PalindromeUtil.isPalindrome(i)) {
                    primePalindromes.add(i);
                }
            }
            if (primePalindromes.isEmpty()) {
                return -1; // 소수이면서 팰린드롬인 수 없음
            }
            return primePalindromes.stream().min(Integer::compare).get();
        }
    }

전체 코드

이제 우리가 구현한 모든 부분을 하나의 프로그램으로 통합해보겠습니다. 아래는 최종적으로 작성된 코드입니다.

public class Main {
        public static void main(String[] args) {
            int start = 10;
            int end = 200;
            int minPrimePalindrome = MinPrimePalindromeFinder.findMinPrimePalindrome(start, end);
            if (minPrimePalindrome != -1) {
                System.out.println("소수이면서 팰린드롬인 수들 중 최솟값: " + minPrimePalindrome);
            } else {
                System.out.println("주어진 범위 내에 소수이면서 팰린드롬인 수가 없습니다.");
            }
        }
    }

테스트 케이스

다음과 같은 범위를 테스트해 볼 수 있습니다:

  • 범위: 10 ~ 200 (결과: 101)
  • 범위: 1 ~ 1000 (결과: 101)
  • 범위: 101 ~ 150 (결과: 131)
  • 범위: 200 ~ 300 (결과: 없음)

결론

이번 포스트에서는 자바를 사용하여 소수이면서 팰린드롬인 수들 중 최솟값을 찾는 문제를 해결하는 방법에 대해 알아보았습니다. 소수 판별 알고리즘과 팰린드롬 체크를 각각 구현한 후, 이를 결합하여 최종적으로 원하는 결과를 얻어냈습니다. 문제를 해결하기 위해 구현한 코드와 함께, 테스트 케이스를 통해 정확성을 검증해 보았습니다.

소수 및 팰린드롬 문제는 알고리즘 시험에서 종종 출제되는 주제이므로, 이러한 문제를 해결하는 방식은 다른 유사한 문제들에도 응용될 수 있습니다. 여러분도 이 글을 참고하여 문제를 해결하는 데 도움을 얻으시기 바랍니다.

참고 자료