[프로그래머스] 소수 찾기 - 자바스크립트

문제

코딩테스트 연습 - 소수 찾기

 

풀이

 

종이 조각이 있다.

종이 조각은 최소 1개, 최대 7개이며 0~9의 숫자로 이루어진다.
"013" 은 0,1,3의 종이 조각이 있다는 의미이다.

 

풀이는 다음과 같다.

 

1. 종이 조각으로 만들 수 있는 모든 숫자를 만들고
2. 각 숫자들이 소수인지 판별하여 소수인 숫자 갯수를 출력한다.

 

종이 조각 "011"의 경우 "011" "11"을 같도록 취급해줘야 한다.

숫자를 만들 때 문자열이 아닌 숫자로 저장해주면 "011"은 11로 저장되므로, 문제가 해결된다.

 

 

종이 조각으로 만들 수 있는 모든 숫자를 구하기 위해서는
모든 종이 조각을 배열에 넣고, 배열의 원소 n개중에 1개 이상을 뽑아 나열하는 모든 경우의 수을 구한다.

 

즉 배열에서 1개, 2개, 3개, ... n개를 뽑는 순열을 구해야 하므로 재귀함수를 이용한다.

 

예를 들어 "17"의 경우 1, 7, 17, 71이 될 수 있다.

 

모든 경우의 수를 배열에 넣었다면 각 원소에 대해 소수를 판별하고, 소수일 때 갯수를 늘려준다.

소수 판별 알고리즘으로는 유명한 에라토스테네스의 체를 사용해도 되고, 무식하게 판별하는 방법(내가 사용한 방법)을 사용해도 된다.

 

코드

function solution(numbers) {
  const N = numbers.length;
  numbers = numbers.split("");
  const arr = [];
  const check = new Array(N).fill(0);

  function dfs(L, str) {
    if (L === N + 1) return;
    if (!arr.includes(+str)) arr.push(+str); // +str의 +가 문자열을 숫자로 형변환해준다.
    for (let i = 0; i < N; i++) {
      if (check[i]) continue;
      check[i] = 1;
      dfs(L + 1, str + numbers[i]);
      check[i] = 0;
    }
  }
  // N개를 선택했다면 더이상 선택할 수 없다.
  // 새로운 종이 조각을 선택할 때 마다 문자열을 숫자화해 배열에 존재하지 않다면 넣어준다.
  // check 배열은 이미 선택한 종이 조각을 중복 선택하지 않기 위해 사용하므로, 재귀 이후에 바로 0으로 해제해준다.
  dfs(0, "");

  let cnt = 0;
  for (let x of arr) {
    if (x < 2) continue;
    let ok = 1;
    for (let i = 2; i < x; i++) {
      if (x % i === 0) {
        ok = 0;
        break;
      }
    }
    cnt += ok; // ok = 1이면 소수이며, ok = 0이 되었다면 소수가 아니다. 그러므로 cnt에 ok 값을 더할 수 있다.
  }
  return cnt;
}