프로그래머스 < 기사단원의 무기 > JavaScript

📍문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/136798

 

📍알고리즘 분류

- 수학

- 구현

 

📍문제 풀이

1 ~ N까지 각 자연수의 모든 약수의 갯수를 빠르게 구하는 문제

 

약수의 갯수를 빠르게 구하려면, 제곱근을 사용하면 된다

 

예를 들어, 100의 약수를 구한다고 생각해보면, 100의 제곱근은 10이다.

전체 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100 인데

1, 2, 4, 5, 10 까지만 구해도 나머지 약수를 계산할 수 있다

 

이를 잘 구현하면 된다

 

📍코드 (JavaScript)

function solution(number, limit, power) {
  const answer = [1]; // 1의 약수는 1이므로 미리 넣어줌
  // 2부터 number 까지 순회
  for (let i = 2; i <= number; i++) {
    const sqrt = Math.sqrt(i); // number의 제곱근
    let count = 0;
    for (let j = 1; j <= sqrt; j++) {
      if (i % j === 0) {
        if (j === sqrt) count++; // 제곱근을 경우 자기 자신과 짝지어지므로 1만 더해줌
        else count += 2; // 나머지 경우는 2 더해줌 (구하지 않을 수까지)
      }
    }
    if (count > limit) answer.push(power);
    else answer.push(count);
  }
  return answer.reduce((acc, cur) => acc + cur, 0);
}