[TIL] 프로그래머스 - 기사단원의 무기(자바스크립트)

나의 처음 풀이

function solution(number, limit, power) {
  let answer = 1
  
  // 1~ number 까지 돌면서 숫자마다 약수를 구함.
  for (let i = 2; i <= number; i++) {
    let count = 0
    for (let j = 0; j < i + 1; j++) {
      if (i % j === 0) {
        count++
      }
    }
    // 약수의 갯수가 limit 보다 크면 answer 에 power 을 더하고 작은경우 약수 갯수를 그대로 더해줌.
    if (count > limit) answer += power
    else answer += count
  }
  return answer
}

이렇게 풀었는데 자꾸 시간초과가 나왔다.
처음에는 풀이가 이상한건가 했는데 이 문제의 경우 약수를 구할 때 공식을 활용해서 약수 구할 때의 연산 횟수를 줄여야 했던 것이다.
예를 들면 8의 약수를 구한다 하면 1,2,4,8 인데 결국
N의 가장 큰 약수는 N을 제외하면 최대 N의 절반이기 때문에 이를 활용하여 약수를 구하는 연산을 줄이면 통과가 된다.

아래는 수정해서 통과한 코드

function solution(number, limit, power) {
  var answer = 0
  for (let i = 1; i <= number; i++) {
    let count = 0
    for (let j = 1; j <= i / 2; j++) {
      if (i % j === 0) {
        count += 1
      }
    }
    count += 1

    if (count > limit) {
      answer += power
    } else {
      answer += count
    }
  }
  return answer
}