알고리즘 문제풀이-소수 찾기

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

소수 찾기

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

---

먼저 구해야하는 것
1.모든 조합으로 만들어진 숫자 배열
2. 소수 판별 함수

수도 코드
문자열인 숫자 각각을 한개의 요소로 배열에 넣어준다.
배열의 순열을 구해준다.(길이가 1개부터 배열 전체가 전부 포함된 순열까지)
문자열이었던 숫자를 숫자로 바꿔주면서 중복되는 경우를 빼준다.
소수인지 판별한다. 소수면 정답 +1

문제풀이

//소수 판별 함수
const isPrime = (num) => {
  if (num === 2) {
    return true;
  } else if (num === 1 || num === 0) {
    return false;
  }

  for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
};
// 모든 숫자만드는 함수
const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((el) => [el]);

  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((el) => [fixed, ...el]);
    results.push(...attached);
  });

  return results;
};
function solution(numbers) {
  var answer = 0;
  let arr = [];
  let arrNum = numbers.split("");

  for (let i = 1; i <= arrNum.length; i++) {
    arr.push(...getPermutations(arrNum, i));
  }//숫자가 1개짜리부터 numbers.length의 개수만큼 다 구해준다.
  let numEle = arr
    .map((el) => Number(el.join("")))
    .filter((item, index, origin) => origin.indexOf(item) === index);
//origin 은 filter 하기 전의 배열
  for (let el of numEle) {
    if (isPrime(el)) {
      answer += 1;
    }
  }

  return answer;
}

수도코드 대로 먼저 순열을 구해주고 중복을 없앤 뒤 소수를 판별해서 리턴값에 넣어줬다.
한가지 아쉬운것은 내가 저 순열에 메모제이션을 활용할 수 있다면 시간복잡도가 좀 더 간단해질 수 있겠다는 생각이 든다. 될지 안될지는 모르겠다만 ㅋㅋ..