[Javascript] 소수 찾기 (42839)

문제링크

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

 

 

접근 방법

주어진 문자열을 길이가 n일때 nP1, nP2, ~~ nPn까지 구한 뒤 
구한 배열 중 소수인 숫자를 찾는 완전 탐색 문제이다.

배운 부분

for (let selectNumber = 1; selectNumber <= numbers.length; selectNumber++) {
    permutationArr.push(
      ...getPermutations(numbers, selectNumber)
        .map((e) => e.join(''))
        .map((e) => parseInt(e))
    );
  }​

 

2차원 배열을 push 받는 부분을 spread 연산자를 통해 쉽게 1차원 배열로 만들 수 있었고,
map을 통해 join한 뒤, 정수로 바꿀 수 있었다.

function solution(numbers) {
  var answer = 0;
  numbers = numbers.split('');
  const permutationArr = [];

  for (let selectNumber = 1; selectNumber <= numbers.length; selectNumber++) {
    permutationArr.push(
      ...getPermutations(numbers, selectNumber)
        .map((e) => e.join(''))
        .map((e) => parseInt(e))
    );
  }

  const permutationSet = [...new Set(permutationArr)].map((e) => parseInt(e));

  permutationSet.forEach((e) => {
    if (isPrime(e)) answer += 1;
  });

  return answer;
}

const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]);

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const permutations = getPermutations(rest, selectNumber - 1);
    const attached = permutations.map((permutation) => [fixed, ...permutation]);
    results.push(...attached);
  });

  return results;
};

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