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

//프로그래머스 코딩테스트 연습 > 완전탐색 > 소수 찾기

 

[문제]

 

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

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

제한사항

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

입출력 예

number/sreturn

"17"	3
"011"	2

입출력 예 설명

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

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

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

 

 

[내가 푼 것]

function solution(numbers) {
  var answer = 0;
  let numbersArr = numbers.split('');
  let allResults = [];

  //모든 조합 구하기
  for (i = 0; i < numbersArr.length; i++) {
    let results = getPermutation(numbersArr, i + 1);
    results = results.map((v) => parseInt(v.join('')));
    allResults = allResults.concat(results);
  }

  //중복 제거
  let uniqSet = new Set(allResults);
  let uniqArr = [...uniqSet];

  //소수가 true인 조합에 대한 개수 구하기
  answer = uniqArr.reduce((cnt, el) => {
    return cnt + isPrime(el);
  }, 0);

  return answer;
}
//순열구하기
function getPermutation(arr, length) {
  let result = [];
  if (length === 1) return arr.map((v) => [v]);
  arr.forEach((v, index, arr) => {
    const selected = v;
    const restArr = arr.filter((_, idx) => idx !== index);
    const perArr = getPermutation(restArr, length - 1);
    const combineFixer = perArr.map((v) => [selected, ...v]);

    result.push(...combineFixer);
  });
  return result;
}
//소수인지 구하기
function isPrime(num) {
  if (num <= 1) {
    return false;
  }
  if (num % 2 === 0) {
    return num === 2 ? true : false;
  }
  const sqrt = parseInt(Math.sqrt(num));
  for (let divider = 3; divider <= sqrt; divider += 2) {
    if (num % divider === 0) {
      return false;
    }
  }
  return true;
}

 

모든 경우의 수(순열)을 뽑고 -> 중복을 제거 -> 소수인지 확인하여 소수면 카운트 누적 -> 반환 했다  

순열 구하는 알고리즘이랑 에라토스테네스의 체가 뭔지 보고 이해하느라 @.@ 오래걸려서

지금 HP가 간당간당해서 다른 사람의 풀이는 다음에 다시 풀 때 볼래 ...

 

 

 

 

 

문제는 여기

 

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

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