약수의_합.md

약수의 합

프로그래머스

문제

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

제한사항

• n은 0 이상 3000 이하인 자연수입니다.

첫 번째 제출 코드

const solution = (n) => {
  let summary = 0;
  for (let i = 1; i <= Math.sqrt(n); i++) {
    if (n % i !== 0) continue;
    const quotient = n / i;
    summary += quotient + i;
  }
  return summary;
};

풀이 과정

1. 자연수 n의 약수를 더해나갈 변수 summary를 초기화한다.
2. n의 약수는 1부터 n까지 1씩 증가시키면서 n을 나누어떨어지게 하는지를 검사하면 된다.
3. 약수는 항상 짝으로 존재하므로 1부터 n까지의 모든 수를 검사하지 않는다. 만약 어떤 수가 n을 나누어떨어지게 했다면 그 수(나눔수)와 몫 모두 n의 약수이다. 따라서 n의 약수를 일렬로 나열했을 때 절반에 해당하는 수까지만 확인한다. 해당 부분은 Math 객체의 sqrt() 메소드로 약수의 절반에 해당하는 값을 구한다.
4. 만약 나누어떨어지지 않는다면 넘어가고, 나누어 떨어진다면 나눔수와 몫을 모두 summary에 더한다.
5. summary를 반환한다.

문제점

n의 약수가 홀수일 때를 생각하지 못했다. 약수는 항상 쌍으로 존재하므로 약수의 개수가 홀수라는 것은 중복되는 약수가 있다는 뜻이다(n의 제곱근이 정수라는 뜻이다.). 중복되는 약수를 처리하는 코드를 짜지 않아서 summary가 기대값보다 커졌다.

해결책

나눔수와 몫이 같은 경우(약수가 중복되는 경우)를 찾아내어 이때는 둘 중 하나만 summary에 더하도록 한다.

두 번째 제출 코드

const solution = (n) => {
  let summary = 0;
  for (let i = 1; i <= Math.sqrt(n); i++) {
    if (n % i !== 0) continue;
    const quotient = n / i;
    const increment = quotient === i ? i : quotient + i;
    summary += increment;
  }
  return summary;
};

풀이 과정

1. 전체적인 논리는 첫 번째 코드와 동일하다.
2. 몫과 나눔수가 같은 값인지의 여부를 삼항연산자로 판단했다. 만약 두 변수의 값이 같다면 나눔수만 summary에 더한다.

잊지말자

• 약수의 개수와 관련된 문제가 나오면 겹치는 약수가 있는 경우를 항상 생각하자.
• 어떤 수의 약수를 구할 때는 1부터 그 수의 제곱근까지를 약수의 후보로 선정하는 것이 가장 효율적이다.