[프로그래머스] Lv.0 소인수분해 JavaScript

Janet·2023년 4월 6일
0

Algorithm

목록 보기
120/314

문제 설명

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


제한사항

  • 2 ≤ n ≤ 10,000

입출력 예

nresult
12[2, 3]
17[17]
420[2, 3, 5, 7]

입출력 예 설명

입출력 예 #1

  • 12를 소인수분해하면 2 2 3 입니다. 따라서 [2, 3]을 return합니다.

입출력 예 #2

  • 17은 소수입니다. 따라서 [17]을 return 해야 합니다.

입출력 예 #3

  • 420을 소인수분해하면 2 2 3 5 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.

문제풀이

💡 문제풀이 과정

  • for() 반복문을 사용하여 i = 2부터 (소수는 2부터 시작하므로), i ≤ n;까지 범위를 설정한다. n을 i로 나누었을 때 나머지는 0이어야 하고, n은 i를 나눈 몫이 된 상태로 계속해서 계속해서 소수로 나누어 마지막 소수가 나올 때까지 나누기를 반복해야 한다. 따라서 for()반복문 안에서 while()문을 사용하여 n % i == 0인 동안 작업을 계속하여 수행하도록 한다. 반복해서 수행할 작업은 n을 i로 나눈 몫으로 계속해서 나누어야 하므로 n = n / i; answer에는 i를 push()한다.
  • n의 소인수들을 배열 형태로 오름 차순 정렬하여 리턴해야 하는데, answer 배열에는 소수들이 모두 들어 있으므로 n의 소인수들이 중복되어 있다. 따라서 new Set()을 이용하면 배열의 중복값을 없애주며 오름 차순으로 반환하기에 sort()는 추가적으로 사용할 필요가 없다. return […new Set(answer)];
  • cf. 소인수분해는 합성수를 소수로 분해하는 것이기 때문에 합성수가 없어질 때까지 계속 나누기를 해야 한다. (합성수: 약수가 3개 이상인 수)

✅ 답안

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

0개의 댓글