프로그래머스 | 소수 조합이 같은지 판단하기

📌 문제

두 정수 A, B를 소인수 분해 했을 때, 공통된 소수의 집합을 가지고 있는 지 판단하는 함수를 작성하세요.

✨ 해결 방법

소인수분해는, 어떤 자연수를 소인수들의 곱으로 표현하는 것을 말합니다.

우선 인수란, 어떤 수나 식을 곱하기로 표현했을 때 곱해지는 각각의 것들을 말합니다. 예를 들어 3 x 4 = 12 = 2 x 6 일 때, 3, 4, 2, 6, 1, 12는 모두 12의 인수입니다. 이는 약수의 개념과 비슷하나 약수는 나눗셈을, 인수는 곱셈을 기준으로 합니다.

이러한 인수 중에서 특별히 소수인 인수를 소인수라고 합니다.
소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다.

소인수분해 하는 방법은 여러가지가 있으나, 가장 쉬운 방법은 자연수를 소수가 나올 때까지 계속 소수로 나누는 것입니다. 예를 들어 60을 소인수분해한다면, 60/2/2/3= 5로, 각 나눈 소수와 몫이 모두 소인수가 됩니다. 따라서 60 = 2² x 3 x 5 입니다. 이를 코드에 적용할 수 있습니다.

💻 solution

function findPrimeFactors(n, prime) {
    for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
        while (n % i === 0) {
            prime.add(i.toString());
            n /= i;
        }
    }
}

function solution(A, B) {
    let primeA = new Set();
    let primeB = new Set();
    let answer = 0;

    findPrimeFactors(A, primeA);
    findPrimeFactors(B, primeB);

    const a = Array.from(primeA).join('');
    const b = Array.from(primeB).join('');

    if (a === b) {
        answer = 1;
    }

    return answer;
}

findPrimeFactors 함수의 범위에 관한 부분은 링크에서 자세하게 다루고 있으니 참고하는 것이 좋습니다.
findPrimeFactors 함수는 prime이라는 배열에 구한 소수를 문자열화해서 넣고 (set 이므로) 정수 n을 그 소수로 나누어서 반복하며 탐색합니다. 이는 위에서 말한 소인수분해 하는 방법을 구현한 것과 같습니다.

solution 함수는, 매개변수로 A, B를 받습니다. 소수를 중복하여 여러 개 받을 필요 없으므로 Set 함수를 각각 선언하고, 소인소분해하는 함수에 넣습니다.

각 소수의 조합이 나온다면, a, b라는 새로운 변수를 생성한 후, 해당 조합을 배열화 (Array.from) 한 후 빈 문자열로 구분하여 하나의 문자열로 합칩니다.

마지막으로, a와 b를 비교하여 두 수의 소수의 조합이 같다면 true (즉, 1)를 반환합니다.