자바스크립트로 순열 만들기!

코딩테스트를 풀다가.. 소수 찾기란 문제를 풀게 되었다.
문제 자체는 길지 않았지만 어떻게 접근해야할지 막막했다.
이래서 자료구조.. 자료구조 하는구나 싶었다.
느낀건 이해하는 것도 물론 중요하지만 어느 정도 외워서 접근하면 더 쉽게 풀 수 있을 것 같은 느낌이었다.

문제

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

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

제한사항

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

입출력 예

입출력 예 설명

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

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

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

문제를 풀기 전에 필요한 지식

소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자의 곱(2×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수나 비소수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

나는 소수를 구할 때 여러가지 방법(에라토스테네스의 체, 소인수분해...)이 있지만 가장 이해하기 쉬운 방법으로 구현했다.

1을 제외하고 그 이후에는 반복문을 통해 2부터 num의 절반까지의 숫자들로 나눠보면서 num이 해당 숫자로 나누어 떨어지는지 확인해서 true, false를 반환한다.

• 만약 num과 나눠진다면 i는 num의 배수이기 때문에 소수가 아니다.
• num의 약수의 갯수는 짝수이기 때문에 2로 나눠서 반만 반복문을 돌려도 된다. chat 선생님은 Math.sqrt를 사용해서 num의 제곱근 까지만 돌려도 된다고 하셨지만 그렇게 했을 때 답을 틀려버려서 나누기 2만했다.

function isPrime(num){
  if(num === 1) return false;
    for(let i = 2; i <= num / 2; i++) {
  		if(num % i === 0) return false;
	} 
  return true
}

순열
수학에서 순열(順列, 문화어: 차례무이, 영어: permutation 퍼뮤테이션[*]) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 정의역과 공역이 같은 전단사 함수이다.

과 같다.
즉, 문제에서 "순서를 고려하여 나열하라", "순열", "순서대로 선택하라"와 같은 표현이 사용되면 순열을 구해야 한다.
위 문제에서는 주어진 숫자로 여러가지 숫자를 만들어야하기 때문에 '순서를 고려해서' 숫자를 만들어야하기 때문에 순열이다!

내 풀이

function solution(numbers) {
    const numArray = numbers.split('');

    // 1. 모든 숫자 조합한 배열 생성 
        // 모든 숫자 조합 생성
    const permutations = new Set();

    const makeCombinations = (arr, str) => {
        if (str.length > 0) pㄴermutations.add(parseInt(str));
        if (arr.length === 0) return;
        for (let i = 0; i < arr.length; i++) {
            const newArr = [...arr];
            newArr.splice(i, 1);
            makeCombinations(newArr, str + arr[i]);
        }
    };

    makeCombinations(numArray, '');
    // console.log(permutations)

    // 3. 소수여부 판별 (filter)
    const resultArr = [...permutations].filter(el => {
        return isPrime(el) && el !== 0 && el !== 1
    })


    // 4. 갯수 카운팅 
    return resultArr.length
}

//소수 구하는 함수.
function isPrime(num){
  if(num === 1) return false;
    for(let i = 2; i <= num / 2; i++) {
  		if(num % i === 0) return false;
	} 
  return true
}

[참고]
소수 : https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)
순열 :
https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4