💻 소수 찾기

❓ 문제

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

✔️ 코드

function solution(numbers) {
    numbers = numbers.split('');
    const isPrime = (n) => {
        if (n <= 1) return false;
        if (n === 2 || n === 3) return true;
        if (n % 2 == 0) return false;
        var divider = 3;
        while (n / 2 > divider) {
            if (n % divider === 0) return false;
            divider += 2;
        }
        return true;
    }
    var pickNumberArr = [];
    const permutation = (arr, n, k) => {
        if (n === arr.length - 1) {
            const str = arr.slice(0, k).join("");
            if (!pickNumberArr.includes(str)) pickNumberArr.push(str);
            return;
        } else {
            for (let i = 0; i < arr.length; i++) {
                var tmp = arr[n];
                arr[n] = arr[i];
                arr[i] = tmp;

                permutation(arr, n + 1, k);
                arr[i] = arr[n];
                arr[n] = tmp;
            }
            return pickNumberArr;
        }
    };
    for (let k = 0; k < numbers.length; k++) {
        permutation(numbers, 0, k + 1);
    }
    var tmp = [];
    for (let i = 0; i < pickNumberArr.length; i++) {
        tmp[i] = Number(pickNumberArr[i]);
    }
    var set = new Set(tmp);
    pickNumberArr = [...set];
    //pickNumberArr.filter(n => isPrime(n) ? true : false);
    var answer = 0;
    pickNumberArr.forEach(n => {
        isPrime(n) ? answer++ : answer;
    })

    return answer;
}
var numbers = "17";
console.log(solution(numbers));

❗️풀이과정

다양한 개념이 들어간다. 이문제는 그냥 한 문자열 숫자를 순열로 조합해서 나올수 있는 모든 숫자 조합을 만들어 놓고 늘어뜨린다음, 늘어뜨린 배열들이 하나씩 소수인가 아닌가 판별해야한다.

소수판별

const isPrime = (n) => {
        if (n <= 1) return false;
        if (n === 2 || n === 3) return true;
        if (n % 2 == 0) return false;
        var divider = 3;
        while (n / 2 > divider) {
            if (n % divider === 0) return false;
            divider += 2;
        }
        return true;
    }

• 1보다 작은경우 소수가 아니다.
• 2혹은 3은 소수이다
• 짝수는 소수가 아니다
• n/2보다 작은 수로 나눠진다면 소수가 아니다.
  • n/2보다 큰수로 애초에 나눠지지 않으므로

순열

  var pickNumberArr = [];
    const permutation = (arr, n, k) => {
        if (n === arr.length - 1) {
            const str = arr.slice(0, k).join("");
            if (!pickNumberArr.includes(str)) pickNumberArr.push(str);
            return;
        } else {
            for (let i = 0; i < arr.length; i++) {
                var tmp = arr[n];
                arr[n] = arr[i];
                arr[i] = tmp;

                permutation(arr, n + 1, k);
                arr[i] = arr[n];
                arr[n] = tmp;
            }
            return pickNumberArr;
        }
    };
    for (let k = 0; k < numbers.length; k++) {
        permutation(numbers, 0, k + 1);
    }

• 기본적인 순열로서 배열에서 배열중에 k를 뽑을 경우 나올수 있는 서로다른 모든 경우를 pickNumberArr에 넣는다.

• 이후 k를 1개 부터 배열의 길이만큼 늘려가며 pickNumberArr에 넣는다

  • (배열에서 나올수 있는 모든 순열)

• 배열중에 k를 뽑을 경우 나올수 있는 서로 다른 모든 경우를 구해보자

  • 첫 문자를 i번째 문자와 스왑하고 다음 문자를 돌리게 해서 재귀함수로 돌린다. 끝에는 k번째 만큼 짜른다음 넣는다.
  • 반환을 할때는 원래대로 돌린다음 반환한다.

배운점

• 소수판별과 순열을 코딩할수 있어야 이문제를 풀수 있다.