[프로그래머스] 기사단원의 무기 문제풀이 JS

1-number까지 약수의 개수를 모두 구해서 더하는데

약수의 개수가 limit를 넘어갔을 때는 해당 위치의 약수의 개수는 power로 계산하면 되는 문제이다.

처음에는 단순히 다 순회를 했을 때는 시간 초과가 나온다.

여기서 시간을 줄여줄 수 있는 방법은

전체를 순회하는게 아니라 제곱이 n이되는 수까지만 확인을 하는 것이다.

이렇게 되면

n=1, i가 1로 1증가

n=2, i가 1로 2증가

n=3, i가 1로 2증가

n=4, i가 1로 2증가, 2로 1증가

....

이런 식으로 수만 확인하면 되서 제곱이 n이되는 수까지만 확인을 하고,

해당 값의 제곱이 현재의 수보다 작을때 수를 증가하면 약수의 개수를 구할 수 있다.

문제에서 limit가 존재하므로 약수의 개수가 limit를 초과하면

count를 power로 바꾸고 해당 반복문을 break하면 시간을 절약할 수 있다!

 

function solution(number, limit, power) {
  let result = 0
  for (let n = 1; n <= number; n++) {
    let count = 0
    for (let i = 1; i * i <= n; i++) {
      if (n % i === 0) {
        count++
        if (i * i < n) count++
      }
      if (count > limit) {
        count = power
        break
      }
    }
    result += count
  }
  return result
}

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