기사단원의무기 - 약수,제곱근

해당 풀이는 일반적으로 반복문을 돌면서 풀면 시간초과가 발생한다.
그래서 약수의 절반만큼계산 or 제곱근만큼만 계산해서 시간초과가 나지않는 방법으로 구현.

• i의 2를 나눈만큼 반복 풀이 = 약수는 본래 값을 제외하고 n/2보다 클 수 없다는것을 이용해 i % j === 0를 이용해 i의 절반만큼만 반복을 돌리고 절반만 돌렸으니 그이후 원래값(i가 4라면 4, 3이라면 3)을 갯수1로 포함해 약수의 갯수로 넣어주는 풀이
• i의 제곱근을 이용한 풀이 = i의 제곱근만큼만 반복문을 돌도록해 i/2 보다 시간복잡도 측면에서 더 유리하다. 규칙이 - 해당 약수를 가지고 입력받은 값을 나누게 될 경우 나오는 결과 값 역시 약수이기 때문
  그래서 먼저 temp라는 배열의 제곱근만큼만 반복돌고 push를 해준이후,
  temp의 길이를 꼭 변수에 담아주고, 변수에 담은 길이 만큼을 반복돌면서 temp배열에 추가로 push해준다. 이때
• i가 1 이라면 temp = [1,1]
• i가 4 라면 temp = [1,2,4,2]
  이렇게 배열에 담기게 된다. 여기서 중복을 제거한 배열의 크기가 약수의 갯수이다.

i의 제곱근을 이용한 풀이

const divisor = (temp, i, divisor) => {
  // temp의 길이는 계속변하기때문에 변수에 담아서 다뤄야함.
  const tempLength = temp.length;

  for (let k = 0; k < tempLength; k++) {
   // 원래값에서 temp에 담긴값을 약수를 나눠서 push
    temp.push(i / temp[k]);
  }

  // 중복제거후 크기를 push
  divisor.push(new Set(temp).size);
};

function solution(number, limit, power) {
  let answer = [];

  for (let i = 1; i <= number; i++) {
    let temp = [];
    for (let j = 1; j <= Math.sqrt(i); j++) {
      
      if (i % j === 0) temp.push(j);
    }
    divisor(temp, i, answer);
  }

  const divisorSum = answer.map(number => {
    if (number > limit) {
      return power;
    } else return number;
  });

  return divisorSum.reduce((acc, cur) => acc + cur, 0);
}

console.log(solution(5, 3, 2));
console.log(solution(10, 3, 2));

i의 2를 나눈만큼 반복 풀이

function solution(number, limit, power) {
  let divisor = [];

  for (let i = 1; i <= number; i++) {
    let divisorCount = 0;
    // 1부터 현재 수의 절반 까지만 반복문을 돌린다.
    // 약수는 본래 값을 제외하고 n/2보다 클 수 없기 때문.
    for (let j = 1; j <= i / 2; j++) {
      if (i % j === 0) {
        divisorCount++;
      }
    }
    // 나머지 본래값 갯수를 추가
    divisorCount++;

    divisor.push(divisorCount);
  }

  const divisorSum = divisor.map(number => {
    if (number > limit) {
      return power;
    } else return number;
  });

  return divisorSum.reduce((acc, cur) => acc + cur, 0);
}

console.log(solution(5, 3, 2));
console.log(solution(10, 3, 2));