[프로그래머스] Lv.2 소수 찾기 JavaScript

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

---

문제풀이

• 가능한 모든 숫자 조합을 생성하고, 각 숫자 조합이 소수인지 여부를 확인하여 소수의 개수를 세기 위한 코드를 작성한다.
• getCombinations 함수는 입력된 숫자로 가능한 모든 조합을 생성하는 역할을 한다. 이 함수는 깊이 우선 탐색 (DFS)을 사용하여 가능한 모든 조합을 찾는다. 각 숫자 조합은 문자열 형태로 저장되며, 이후 정수로 변환되어 반환된다.
• isPrime 함수는 주어진 숫자가 소수인지를 판별한다. 이 함수는 숫자가 2보다 작거나, 2로 나누어지지 않는지, 제곱근까지의 모든 숫자로 나누어지지 않는지를 확인하여 소수 여부를 판단한다.
• 마지막으로, solution 함수는 getCombinations 함수를 사용하여 가능한 모든 조합을 생성하고, 중복된 조합을 제거한다. 그런 다음 isPrime 함수를 사용하여 각 조합이 소수인지를 확인하고, 소수인 조합의 개수를 반환한다. 가능한 모든 조합을 생성하고 중복을 제거하기 위해서 Set을 사용하였다.

✅ 답안

function solution(numbers) {
  const set = [...new Set(getCombinations(numbers))];
  return set.filter((v) => isPrime(v)).length;
}

const getCombinations = (str) => {
  const answer = [];
  let visited = new Array(str.length).fill(false);

  const dfs = (cur) => {
    answer.push(+cur);
    for (let i = 0; i < str.length; i++) {
      if (!visited[i]) {
        visited[i] = true;
        dfs(cur + str[i]);
        visited[i] = false;
      }
    }
  };

  dfs('');
  return answer;
};

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