[프로그래머스] Level1. 약수의 개수와 덧셈

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

---

제한 사항

1 ≤ left ≤ right ≤ 1,000

---

입출력 예

---

내가 풀었던 방법은 다음과 같다.

function solution(left, right) {
  let answer = 0;

  for (let i = left; i <= right; i++) {
    let count = 0;
    for (let j = 1; j <= i/2; j++) { // 본인을 제외하고 약수는 num/2 보다 작음
      if (i % j === 0) count++;
    }
    count++;  // 본인 값까지 추가
    answer += count % 2 === 0 ? i : -i;
  }

  return answer;
}

left부터 right까지 반복문을 돌려주고 그 안에서 또 다른 반복문으로 현재 계산하고 있는 수의 절반 값까지 체크하여 약수일 경우 count 횟수를 더해준 뒤, 마지막으로 무조건 약수인 본인이 있기에 count를 한 번 더 더해주었다.

그렇게 얻은 count 값으로 약수의 개수 홀짝 판별을 해 answer를 구했다.

---

근데 나중에 다른 풀이를 찾아보다가 제곱근을 사용하면 훨씬 간단하고 더 낮은 시간 복잡도를 갖는 풀이를 할 수 있다는 걸 알게 되었다.

약수의 개수는 기본적으로 짝수인데, 어떤 수의 제곱인 경우(제곱근)에만 약수의 개수가 홀수임을 이용하는 것이다.

약수는 원래 나누어 떨어지는 수이므로 각각 곱해서 원래 수가 되는 짝이 있지만, 제곱수인 경우는 자기 자신을 두 번 곱하기 때문에 약수가 홀수가 된다.

따라서 제곱수 === 약수 개수 홀수

그리고 제곱수는 무조건 제곱근이 정수이기에, Number.isInteger를 사용하여

i의 제곱근이 정수인 경우 -> 제곱수 -> 약수 개수 홀수 -> answer -= i

아니면 answer += i 하도록 코드를 작성했다.

다시 풀어본 풀이는 다음과 같다!

function solution(left, right) {
    let answer = 0;
    for (let i=left; i<=right; i++) {
        answer += Number.isInteger(Math.sqrt(i)) ? - i : i 
    }
    return answer;
}