재고 코드 중 소수 번호 개수

자바스크립트 코딩테스트 문제로 sieve-of-eratosthenes 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium sieve-of-eratosthenes 함수명: countPrimeStockCodes 제한 시간: 300ms

여러 재고 코드 번호가 주어졌을 때, 그중 소수인 번호가 몇 개인지 세는 문제입니다.

문제 설명

정수 배열 codes가 주어집니다.

각 값은 재고 코드에 붙은 번호입니다. 번호가 소수라면 특별 검수 대상이라고 합니다.

소수인 재고 코드 번호의 개수를 반환하는 countPrimeStockCodes 함수를 작성하세요.

같은 번호가 여러 번 등장하면 서로 다른 재고 코드로 보고 각각 개수에 포함합니다.

제한사항

0 <= codes.length <= 100000
0 <= codes[i] <= 100000
소수는 1보다 큰 자연수 중 1과 자기 자신으로만 나누어떨어지는 수입니다.
0과 1은 소수가 아닙니다.
같은 소수 번호가 여러 번 나오면 등장한 횟수만큼 셉니다.
반환값은 소수인 번호의 개수입니다.

예시

입력: codes = [2, 3, 4, 5, 10, 11] -> 출력: 4
입력: codes = [0, 1, 1, 4, 6, 8] -> 출력: 0
입력: codes = [17, 17, 18, 19, 20] -> 출력: 3
입력: codes = [] -> 출력: 0

힌트

각 숫자마다 2부터 나누어 보면 입력이 길 때 느려질 수 있습니다.
먼저 codes의 최댓값을 구하고, 그 값까지의 소수 여부를 한 번에 표시해 보세요.
에라토스테네스의 체에서는 어떤 수가 소수로 남아 있으면 그 수의 배수들을 합성수로 지웁니다.

해설

이 문제는 여러 숫자의 소수 여부를 반복해서 확인해야 합니다. 숫자 하나마다 나눗셈으로 소수 판별을 하면 같은 범위의 정보를 계속 다시 계산하게 됩니다.

핵심은 에라토스테네스의 체로 가능한 모든 번호의 소수 여부를 미리 구해 두는 것입니다.

먼저 배열이 비어 있으면 바로 0을 반환할 수 있습니다. 그렇지 않다면 codes에서 가장 큰 값을 찾습니다. 최댓값이 1 이하라면 소수가 없으므로 역시 0입니다.

그다음 길이가 max + 1인 불리언 배열 isPrime을 만들고 처음에는 모두 true로 둡니다. 단, 0과 1은 소수가 아니므로 false로 바꿉니다.

이제 p를 2부터 보면서 p * p <= max인 동안 반복합니다. isPrime[p]가 true라면 p는 소수입니다. 이때 p * p, p * p + p, p * p + 2p처럼 p의 배수들을 모두 false로 바꿉니다. p * 2가 아니라 p * p부터 지워도 되는 이유는, 그보다 작은 배수들은 이미 더 작은 소수의 배수로 지워졌기 때문입니다.

체를 만든 뒤에는 codes를 한 번 더 순회하면서 isPrime[code]가 true인 값만 셉니다. 같은 소수가 여러 번 나오면 각 재고 코드가 따로 존재하는 것이므로 매번 count를 증가시킵니다.

최댓값을 m, 배열 길이를 n이라고 하면 체를 만드는 데 O(m log log m), 입력을 세는 데 O(n)이 걸립니다. 공간 복잡도는 소수 여부 배열 때문에 O(m)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과