🔎프로그래머스 - 소수 찾기

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42839

카테고리: 완전 탐색

출처: 프로그래머스 코딩 테스트 고득점 Kit, https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

✏️ 내 풀이

주어진 배열의 각 수를 붙여 만들 수 있는 모든 경우의 수를 재귀를 이용해 탐색하고, 소수인지 판별해서 총 소수의 개수를 리턴한다.

🗒️ 내 코드

const isPrime = (num) => {
  if (num < 2) {
    return false;
  }

  if (num == 2) {
    return true;
  }

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

const dfs = (set, arr, str) => {
  if (arr.length >= 1) {
    for (let i = 0; i < arr.length; i++) {
      let newStr = str + arr[i];
      let newArr = [...arr];
      newArr.splice(i, 1);

      if (isPrime(parseInt(newStr))) {
        set.add(parseInt(newStr));
      }

      dfs(set, newArr, newStr);
    }
  }
};

function solution(numbers) {
  let nums = numbers.split("");
  let set = new Set();
  dfs(set, nums, "");

  return set.size;
}