이번에 푼 문제는 프로그래머스의 소수 만들기 문제이다.
코딩테스트 연습 - 소수 만들기
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
nums | result |
---|---|
[1,2,3,4] | 1 |
[1,2,7,6,4] | 4 |
에라토스테네스 체를 이용한 소수 배열 만들기:
n은 최대 1000이며 3개의 숫자를 더해주므로 3001크기의 배열을 만들어준다. 그리고 에라토스테네스 체를 이용해 3000까지의 수 중에서 소수인 수를 판별하는 numArr 배열을 구한다.
3중 for문을 이용해 가능한 모든 조합들이 소수인지 판별하기:
sum = nums[i] + nums[j] + nums[k]
로 배열의 서로다른 3개의 원소를 더한 후, 해당 sum이 소수일 시 answer을 1 더해준다.
// 가능한 모든 조합이 소수인지 판별하는 과정
function solution(nums) {
let answer = 0;
let arrLen = nums.length;
const primeArr = makePrime();
for (let i = 0; i < arrLen - 2; i++) {
for (let j = i+1; j < arrLen - 1; j++) {
for (let k = j+1; k < arrLen; k++) {
let sum = nums[i] + nums[j] + nums[k];
(primeArr[sum]) && answer++;
}
}
}
return answer;
}
// 에라토스테네스 체를 이용해 3000까지의 수 중 소수인 수를 판별
function makePrime () {
const numArr = new Array(3001).fill(true);
for (let i = 2; i**2 <= 3000; i++) {
if (!numArr[i]) continue;
for (let j = i**2; j <= 3000; j+= i) {
numArr[j] = false;
}
}
return numArr;
}