소인수 분해 - 프로그래머스

코딩테스트 - 소인수 분해

소인수 분해란 소수들의 곱으로 표현하는 것을 말한다. 그리고 소인수란 주어진 자연수를 나누었을 때, 약수가 소수 즉 1 하나만 있는 경우의 수를 말한다. 말 그대로 소인수이다. 먼 옛날... 수학 시간이 갑자기 떠올랐다..

그러하다. 소인수 분해란 어떠한 자연수를 나누었을 때, 이런 소인수들로만 이루어진 집합을 말한다.

처음 시도한 로직

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 2 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

1. 문제를 보고 가장 먼저 떠오른 것은 어쨌든 소인수들의 집합을 만들고, 그 소인수가 중복이 있다면 new Set()객체를 통해서 중복을 제거하면 되겠다고 생각했다.

2. 여기서 어떻게 소인수들의 집합을 만들어낼 수 있을까?

반복문을 통해 2일 때, 나눠주고 3일 때 나눠주고 4일 때 나눠주고 5일 때 나눠주고를 반복하면서 이 중 나눠지는 숫자가 소인수 인지를 판별하고 소인수라면 한 배열에 담고 아니라면 다음 숫자로 넘어가게 만들면 된다.

3. 늘 생각은 잘한다... 그리고 이걸 코딩으로 못 옮긴다. 여러 블로그와 풀이들을 보면서 답을 만들었다.

제출한 답.

function solution(n) {
    var answer = [];
    
    for(let i =2 ; i<=n ; i++) {
        
        while( n % i === 0) {
            answer.push(i);
            n = n / i;
        }
        
    }
    
    return [...new Set(answer)];
}

1. 소인수들의 집합(중복도 가능)을 넣어둘 빈 배열 answer를 만들어준다.
2. for문을 통해서 매개변수로 들어오는 n을 i로 나눈다.
3. 그리고 while문의 조건을 만족하면 i를 계속 반복해서 나눠준다.

• 조건문은 n을 i로 나누었을 때 나머지가 0으로 약수인지를 판별한다.
• 그리고 n을 i로 나눈 값으로 갱신한다. 왜? 나눈 값으로 n을 갱신해야 소인수를 꺼낼 수 있다.

ex
1) n=500이라고 한다면, i는 처음에 2로 시작할 것이다. 500 % 2===0 이기 때문에 while문을 통해 반복하고 그때의 i인 2는 answer 배열에 쌓인다. 그리고 n = 500 / 2 즉, 250으로 갱신된다.
2) 다시 while문이 돌아간다. 250 % 2 === 0 이기 때문에 answer에 다시 2가 들어가고 n = 125로 갱신된다.
3) 125 % 3 === 0 아니기 때문에 i는 4로 넘어간다. 125 % 4 === 0 이 아니기 때문에 5로 넘어간다. 125 % 5 === 0이기 때문에 5를 나눠주는 것을 반복한다. 여기서 2는 소인수로 들어 갔는데 4는 안 되는 이유는 명확하다. 이미 앞에서 2가 2번 나눠졌기 때문이다. 그럼 4를 나눌 필요가 없다.

4. 그렇게 소인수가 중복으로 쌓이면 마지막에 new Set객체를 통해서 중복을 제거해준다.