이 강좌에서는 자바스크립트 코딩테스트 문제를 해결하는 방법을 다루고자 합니다. 문제의 주제는 소수와 팰린드롬 수 중에서 최솟값을 찾는 것입니다. 이 문제를 해결하기 위해 필요한 알고리즘과 함께, 문제해결 과정을 단계별로 안내할 것입니다.
문제 정의
주어진 정수 N이 있습니다. 1부터 N까지의 모든 숫자 중에서 소수이면서 팰린드롬인 수들 중에서 최솟값을 찾아야 합니다. 만약 그런 수가 존재하지 않으면 -1을 반환합니다.
문제 예시
- 입력: N = 31
출력: 3 (소수: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 중에서 팰린드롬인 수는 3) - 입력: N = 11
출력: 11 (소수인 11은 팰린드롬 수) - 입력: N = 1
출력: -1 (1은 소수도, 팰린드롬 수도 아님)
문제 해결 접근법
문제를 해결하기 위해 다음과 같은 방법을 사용할 것입니다.
- 1부터 N까지의 수 중에서 소수를 찾습니다.
- 찾은 소수들 중에서 팰린드롬인 수를 걸러냅니다.
- 팰린드롬 수 중에서 최솟값을 찾습니다.
단계별 구현
1단계: 소수 찾기
소수를 찾기 위해엔 간단한 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용할 수 있습니다. 이 알고리즘은 O(n log log n)의 시간 복잡도로 소수를 찾을 수 있는 효율적인 방법입니다.
function findPrimes(n) {
const isPrime = Array(n + 1).fill(true);
isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아닙니다.
for (let i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (let j = i * i; j <= n; j += i) {
isPrime[j] = false; // i의 배수를 소수에서 제외
}
}
}
const primes = [];
for (let i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.push(i);
}
}
return primes;
}2단계: 팰린드롬 수 찾기
팰린드롬 수는 정수 형태의 숫자가 정방향과 역방향이 동일한 수를 의미합니다. 예를 들어, 121, 1331 등입니다.
function isPalindrome(num) {
const str = num.toString();
return str === str.split('').reverse().join('');
}3단계: 최솟값 찾기
이제 소수이면서 팰린드롬인 수들을 모아 최솟값을 찾으면 됩니다.
function findMinPalindromicPrime(n) {
const primes = findPrimes(n);
const palindromicPrimes = primes.filter(isPalindrome);
return palindromicPrimes.length > 0 ? Math.min(...palindromicPrimes) : -1;
}전체 코드
이제 모든 단계를 결합한 최종 코드를 확인해보겠습니다.
function isPalindrome(num) {
const str = num.toString();
return str === str.split('').reverse().join('');
}
function findPrimes(n) {
const isPrime = Array(n + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (let j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
const primes = [];
for (let i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.push(i);
}
}
return primes;
}
function findMinPalindromicPrime(n) {
const primes = findPrimes(n);
const palindromicPrimes = primes.filter(isPalindrome);
return palindromicPrimes.length > 0 ? Math.min(...palindromicPrimes) : -1;
}
// 사용 예시
console.log(findMinPalindromicPrime(31)); // 출력: 3
console.log(findMinPalindromicPrime(11)); // 출력: 11
console.log(findMinPalindromicPrime(1)); // 출력: -1결론
이번 강좌에서는 소수와 팰린드롬 수 중에서 최솟값을 찾는 문제를 해결하기 위한 알고리즘을 구현해보았습니다. 에라토스테네스의 체를 사용하여 효율적으로 소수를 찾고, 팰린드롬 수를 확인하며, 최종적으로 조건에 맞는 최솟값을 찾아내는 과정을 살펴보았습니다. 이런 문제를 풀기 위해서는 알고리즘적 사고와 함께 프로그래밍 능력 또한 필요합니다. 앞으로도 다양한 코딩 문제를 통해 실력을 다져나가길 바랍니다.