Algorithm - lev1 소수 만들기

프로그래머스 level 1 소수 만들기

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

내 풀이 (100/100)

function solution(nums) {
  let count = 0;
  const arr = [];
  // 모든 경우의 수 배열에 저장
  for (let i = 0; i <= nums.length - 3; i++) {
    for (let j = i + 1; j <= nums.length - 2; j++) {
      for (let k = j + 1; k <= nums.length - 1; k++) {
        arr.push(nums[i] + nums[j] + nums[k]);
      }
    }
  }
  
  // 배열의 모든 요소 소수 검사하고 조건에 맞는 경우 count +1
  arr.forEach((e) => {
    const arr = [];
    for (let i = 1; i <= e; i++) {
      if (e % i === 0) {
        arr.push(i);
      }
    }
    if (arr.length === 2) {
      count += 1;
    }
  });
  return count;
}

• 계속 3중첩 반복문밖에 떠오르지 않아 다른 방법이 있을까하다가 그냥 3중첩 반복문을 썼는데, 풀이도 3중첩 반복문이라 안심했다. 나와 다른 점은 나는 모든 경우에 수에 대해 또 다시 2중첩 반복문을 사용했는데, 하단 다른 사람의 풀이는 제곱근을 이용하여 소수를 구했다는 점이다. 이렇게 하면 1중첩 반복문으로 데이터를 절반으로 줄여서 검사할 수 있기 때문에 성능이 더 올라간다. 이런 수학적 지식은 머리속에 박아놔야겠다.

다른 사람 풀이

function solution(nums) {
  let answer = 0;
  const length = nums.length;
  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      for (let k = j + 1; k < length; k++) {
        const sum = nums[i] + nums[j] + nums[k];
        if (isPrime(sum)) answer += 1;
      }
    }
  }

  return answer;
}

function isPrime(num) {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return num >= 2;
}