[JS]소수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/12977?language=javascript 

프로그래머스

제출 코드

 

function solution(nums) {
const r = 3;

const combination = (arr, k) => {
    const answer = [];
    const comb = [...Array(k)].fill(0);
    backTracking(answer, comb, arr, k, 0, 0);
    return answer;
};

const backTracking = (answer, comb, arr, k, idx, start) => {
    if (idx === k) {
        return answer.push([...comb]);
    }
    
    for (let i=start; i<arr.length; i++) {
        comb[idx] = arr[i];
        backTracking(answer, comb, arr, k, idx+1, i+1);
    }
}

const trialDivision = (number) => {
    // Check if number is integer.
    if (number % 1 !== 0) {
        return false;
    }

    if (number <= 1) {
        // If number is less than one then it isn't prime by definition.
        return false;
    }

    if (number <= 3) {
        // All numbers from 2 to 3 are prime.
        return true;
    }

    // If the number is not divided by 2 then we may eliminate all further even dividers.
    if (number % 2 === 0) {
        return false;
    }

    // If there is no dividers up to square root of n then there is no higher dividers as well.
    const dividerLimit = Math.sqrt(number);
    for (let divider = 3; divider <= dividerLimit; divider += 2) {
        if (number % divider === 0) {
        return false;
        }
    }

    return true;
}

const numCombination = combination(nums, r)

const sumOfNum = numCombination.map(e => e).map(el => el.reduce((acc,cur) => acc + cur))

return sumOfNum.map(e => trialDivision(e)).reduce((acc,cur) => {
    if(cur === true) {
        acc = acc + 1
    }
    return acc}
,0)
}

풀이에 접근한 과정

 

1. 배열에서 3개 숫자를 "어떻게" 조합할 것인가?

2. 조합한 숫자의 합이 소수인지 "어떻게" 판단할 것인가?

 

[1,2,3,4]라는 배열이 있다고 가정을 하고, 여기서 "3가지"를 뽑을 수 있는 조합을 하나하나 작성하였습니다.

 

[1,2,3] [1,2,4], [1,3,4], [2,3,4] ->  4가지가 있었습니다.

 

입력되는 배열 nums는, "3개 이상" (숫자가 모자랄 일을 고민하지 않아도 됩니다.) "50개 이하" 중복 없이 (중복 고려 x) 랜덤입니다.

 

즉 n개중 3개를 뽑아내야 했습니다.

 

수학의 개념을 찾던 중 "조합"을 알게 되었고, nCr로 나타내며 앞에 n이 총 경우의 수, r이 그중 뽑아낼 개수였습니다.

 

이 문제는 nC3이 되는 것으로 고정되었습니다.

 

조합의 경우의 수를 세는 법은 10C3 기준

 

10 * 9 * 8

   ㅡ

3 * 2 * 1

 

 

 

n * n-1 * n-2...(r의 개수만큼)

      ㅡ

r * r-1 * r-2...(r의 개수만큼)으로 정해졌습니다.

 

개수를 구하는 문제라면 쉽게 풀었겠지만 여기서는 개수를 구하는 문제는 아니었습니다.

 

---

다음으로 필요한 지식은 소수에 대한 정의입니다.

 

소수란, 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.

---

위의 두 가지 수학 지식을 따라 조합을 뽑는 함수, 백트래킹을 하는 함수, 소수인지를 판별하는 함수 3가지를 미리 만들어둔 뒤 매개변수로 받아서 가공한 작업을 진행하였습니다.

 

하단 자료를 참고하였으며, 하단 자료에 대한 설명을 포스팅하도록 하겠습니다.

 

---

참고 자료

https://github.com/trekhleb/javascript-algorithms/blob/master/README.ko-KR.md

GitHub - trekhleb/javascript-algorithms: 📝 Algorithms and data structures implemented in JavaScript with explanations and lin

https://velog.io/@dev-redo/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EB%A1%9C-%EC%A1%B0%ED%95%A9%EC%9D%84-%EA%B5%AC%ED%98%84%ED%95%B4%EB%B3%B4%EC%9E%90-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

[알고리즘] 자바스크립트로 조합을 구현해보자! - 백트래킹