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

풀이 과정

dfs

• 재귀 실행 후 반복 여부를 다시 false로 바꿔두어야 다음 for 반복문의 재귀에 영향을 미치지 않음

코드

function solution(numbers) {
  const set = new Set();
  const q = [];
  const visited = Array(numbers.length).fill(false);
  const dfs = (str) => {
    if (str) q.push(Number(str));
    if (isPrime(Number(str))) set.add(Number(str));
    for (let i = 0; i < numbers.length; ++i) {
      if (visited[i]) continue;
      visited[i] = true;
      dfs(str + numbers[i]);
      visited[i] = false;
    }
  };
  dfs('');
  return set.size;
}

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;
}

🦾

dfs라는 것까지 감이 왔는데 도저히 안 풀려서 다른 사람들의 풀이를 참고했다.
핵심은 재귀를 실행한 후에 다시 visited를 false로 바꾸는 것이었다.