[프로그래머스 Lv2] 소수 찾기

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

우선 크게 두가지가 보인다.

1. dfs로 경우의수를 모두 찾기(대신 0으로 시작하는 수는 0을 없앤 수와 같음)
2. 소수를 판별하는 함수

문제가 dfs를 통해서 풀 수 있다는 것은 알았는데 dfs를 통해서 순열,조합 문제를 여러 번 풀었는데도 아직 감이안잡힌다..

풀이

소수 구하기

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

소수를 판별하는데는 제곱수를 통한 방법을 사용하였다.(N의 약수는 무조건 sqrt(N)의 범위에 존재한다.)
에라토스테네스의 체를 사용해도 된다.

dfs

function dfs(set, arr, fixed) {
  if (arr.length >= 1) {
    for (let i = 0; i < arr.length; i++) {
      let newFixed = fixed + arr[i];
      let copyArr = [...arr];
      copyArr.splice(i, 1);

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

      dfs(set, copyArr, newFixed);
    }
  }
}

for문을 돌때마다 매번 수들 중 하나를 선택하고 newFixed는 지금까지 선택된 수 문자열, copyArr은 선택되고 남은 수 문자열, set은 소수인 수를 담고있으므로 최종적으로 set의 사이즈가 답이된다.

주의할점은 소수를 판별할때는 문자열로 넘겨도 되지만("011", "11") set에 넣을때는 "011"과 "11"은 다르게 인식하므로 중복을 제거하기 위해서 정수로 변환해서 넣어야 한다.

코드

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

function dfs(set, arr, fixed) {
  if (arr.length >= 1) {
    for (let i = 0; i < arr.length; i++) {
      let newFixed = fixed + arr[i];
      let copyArr = [...arr];
      copyArr.splice(i, 1);

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

      dfs(set, copyArr, newFixed);
    }
  }
}

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

  dfs(set, nums, "");

  return set.size;
}

console.log(solution("011"));

출처

https://velog.io/@im_hass_/Level2.-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0