[프로그래머스] 소수 만들기 | JavaScript

문제출처

1. 문제

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 설명

입출력 예 #1

[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2

[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

2. 풀이

이전에 소수를 찾는 문제를 풀면서 에라토스테네스 체를 이용하는 방법을 배웠다.
그래서 이번 문제도 유사한 문제라서 에라토스테네스 체를 이용하여 문제를 풀었다.

• 배열의 값 중 3개의 숫자를 더해 나올 수 있는 최댓값을 구한다.
• 에라토스테네스 체 이용하여 index가 소수라면 true, 아니라면 false로 표시되는 배열을 만든다.
• 3중 for문을 이용하여 배열의 합 중 소수 배열에 true로 표시되어 있다면 res 값을 증가시킨다.

function solution(nums) {
  let res = 0; // 소수 개수
  
  // nums 오름차순 정렬하여 뒤에서 3개 합 구해서 나올 수 있는 최댓값 구하기
  let max_num = nums
    .sort((a, b) => a - b)
    .reduce((acc, cur, idx) => (idx > nums.length - 4 ? acc + cur : null), 0);

  // 에라토스테네스 체 이용하여 소수 배열 만들기(index가 소수라면 true, 소수가 아니라면 false)
  let prime_arr = Array(max_num + 1).fill(true);
  prime_arr[0] = false;
  prime_arr[1] = false;
  for (let i = 2; i * i <= max_num; i++) {
    if (prime_arr[i]) {
      for (let j = i * i; j <= max_num; j += i) {
        prime_arr[j] = false;
      }
    }
  }

  for (let i = 0; i < nums.length - 2; i++) {
    for (let j = i + 1; j < nums.length - 1; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        // 배열에서 3개의 숫자의 합이 소수 배열에 있다면 res 증가시키기
        if (prime_arr[nums[i] + nums[j] + nums[k]]) res ++;
      }
    }
  }
  return res;
}

3. 다른 사람의 풀이

내가 에라토스테네스 체를 이용하여 소수 배열을 따로 만든 것과 달리, 3개의 숫자를 더할 때마다 primecheck() 함수를 이용하여 소수인지 판별하는 방식도 있다.

이렇게 푸는 게 더 직관적이고 간단해 보인다.

// 소수 판별
function primecheck(n) {
  for (var i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

function solution(nums) {
  var cnt = 0;
  for (var i = 0; i < nums.length - 2; i++) {
    for (var j = i + 1; j < nums.length - 1; j++) {
      for (var w = j + 1; w < nums.length; w++) {

        if (primecheck(nums[i] + nums[j] + nums[w])) {
          cnt++;
        }
      }
    }
  }
  return cnt;
}