소수 찾기 (프로그래머스)

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

function permutation(arr, n) {
  const result = [];

  if (n === 1) {
    return arr.map((item) => [item]);
  } else {
    arr.forEach((fixed, idx, arr) => {
      const rest = arr.filter((_, index) => idx !== index);
      const combis = permutation(rest, n - 1);
      const combine = combis.map((v) => [fixed, ...v]);
      result.push(...combine);
    });
  }

  return result;
}

function solution(num) {
  const startArray = num.split('');
  const stack = [];
  let answer = 0;

  for (let i = 1; i < num.length + 1; i++) {
    stack.push(...permutation(startArray, i).map((v) => Number(v.join(''))));
  }

  const newSet = new Set(stack);
  newSet.forEach((v) => {
    if (isPrime(v)) {
      answer += 1;
    }
  });

  return answer;
}

console.log(solution('17'));

=> 다 구해놓고 빡치게 소수 판별하는 부분에 로직 문제가 있음을 파악함. 기존에 했던 에라토스테네스의 알고리즘 중 취약한 부분을 발견하였다. n이 클 경우 배열 생성을 못한다는 단점이 있음. 따라서 소수 판별 함수를 수정하였음.