자바스크립트 코딩테스트 강좌, 신기한 소수 찾기

문제 설명

수학적으로 정의된 소수(Prime Number)는 1과 자기 자신 외에 다른 약수를 가지지 않는 자연수입니다. 예를 들어, 2, 3, 5, 7, 11, 13 등은 소수에 해당합니다. 이번 문제에서는 신기한 소수를 찾아야 합니다. 신기한 소수란 특정 기준에 의하여 판별되는 소수를 의미합니다.

문제 정의

주어진 정수 N에 대해, N보다 작은 모든 신기한 소수를 찾아 배열로 반환하세요. 신기한 소수는 다음의 기준을 따른다고 가정합니다:

  1. 신기한 소수는 2 이상의 자연수여야 한다.
  2. 소수의 각 자릿수의 합이 10을 초과하면 신기한 소수가 아니다.
  3. 각 자릿수는 짝수보다 홀수의 자릿수가 더 많아야 한다.
  4. 각 자릿수는 반드시 정수여야 하며, 음수를 포함해선 안 된다.

입력 및 출력 형식

입력: 양의 정수 N (2 ≤ N ≤ 10,000)
출력: 정수 배열 (신기한 소수들)

문제 풀이 과정

단계 1: 소수 판별 함수 구현

소수를 판별하는 함수를 구현합니다. 이 함수는 입력된 숫자가 소수인지 여부를 확인해야 합니다. 이때 소수의 정의에 따라 2부터 시작하여 해당 숫자의 제곱근까지 나누어 떨어지는지 검사합니다.

function isPrime(num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 === 0 || num % 3 === 0) return false;

        for (let i = 5; i * i <= num; i += 6) {
            if (num % i === 0 || num % (i + 2) === 0) return false;
        }
        return true;
    }

단계 2: 신기한 소수 판별 함수 구현

신기한 소수를 판별하는 함수를 구현합니다. 이 기능은 주어진 숫자의 자릿수의 합과 자릿수를 세는 기능을 포함해야 합니다.

function isCuriousPrime(num) {
        if (!isPrime(num)) return false;

        const digits = num.toString().split('').map(Number);
        const sumOfDigits = digits.reduce((acc, digit) => acc + digit, 0);
        const oddCount = digits.filter(digit => digit % 2 !== 0).length;
        const evenCount = digits.filter(digit => digit % 2 === 0).length;

        return sumOfDigits <= 10 && oddCount > evenCount;
    }

단계 3: 결과 생성 함수 구현

이제 입력된 N보다 작은 모든 신기한 소수를 찾기 위한 메인 함수인 findCuriousPrimes를 생성합니다.

function findCuriousPrimes(N) {
        const curiousPrimes = [];
        for (let i = 2; i < N; i++) {
            if (isCuriousPrime(i)) {
                curiousPrimes.push(i);
            }
        }
        return curiousPrimes;
    }

단계 4: 전체 코드 및 예제 실행

위에서 작성한 함수들을 통합하여 전체 코드를 완성합니다. 아래는 최종적인 코드 예제입니다.

function isPrime(num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 === 0 || num % 3 === 0) return false;

        for (let i = 5; i * i <= num; i += 6) {
            if (num % i === 0 || num % (i + 2) === 0) return false;
        }
        return true;
    }

    function isCuriousPrime(num) {
        if (!isPrime(num)) return false;

        const digits = num.toString().split('').map(Number);
        const sumOfDigits = digits.reduce((acc, digit) => acc + digit, 0);
        const oddCount = digits.filter(digit => digit % 2 !== 0).length;
        const evenCount = digits.filter(digit => digit % 2 === 0).length;

        return sumOfDigits <= 10 && oddCount > evenCount;
    }

    function findCuriousPrimes(N) {
        const curiousPrimes = [];
        for (let i = 2; i < N; i++) {
            if (isCuriousPrime(i)) {
                curiousPrimes.push(i);
            }
        }
        return curiousPrimes;
    }

    console.log(findCuriousPrimes(50));  // Example Output: [3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47]

최적화 방안

현재 구현된 알고리즘은 N에 비례하는 시간복잡도를 가지며, 개선 가능성이 있습니다. 소수를 먼저 미리 계산하여 배열에 저장해놓고, 이 배열을 이용해 신기한 소수를 찾는 방식으로 최적화 할 수 있습니다.

결론

이 글에서는 자바스크립트로 신기한 소수를 찾는 방법을 다루었습니다. 알고리즘을 단계별로 나누어 설명하였으며, 최종적인 코드도 포함하였습니다. 이 문제를 풀어보면서 자바스크립트의 조건문, 반복문 및 배열 조작에 대한 이해를 깊이 있게 할 수 있습니다.

참고 자료 및 Links