[프로그래머스] 약수의 합

문제 설명: 주어진 숫자 n의 모든 약수들의 합을 구하는 문제입니다. 예를 들어, n이 12일 때 약수는 1, 2, 3, 4, 6, 12이며, 이들의 합은 28입니다.

약수를 구하는 방법: 약수의 공통점은 n % i == 0이라는 것입니다. 예를 들어, 12의 약수들을 보면 다음과 같습니다:

• 12 % 1 == 0
• 12 % 2 == 0
• 12 % 3 == 0
• 12 % 4 == 0
• 12 % 6 == 0
• 12 % 12 == 0

즉, n의 약수를 구하기 위해 1부터 n까지의 수를 반복하면서 n % i == 0인 i를 찾으면 됩니다.

이를 코드로 구현하면 다음과 같습니다:

for (int i = 1; i <= n; i++) {
    if (n % i == 0){
        ...
    }
}

 

더 효율적인 방법: 위의 방법은 1부터 n까지 모두 반복하기 때문에 비효율적일 수 있습니다. 약수의 또 다른 특징을 이용해 더 효율적으로 해결할 수 있습니다.

n이 12일 때 약수는 1, 2, 3, 4, 6, 12입니다. 이들의 공통점은 다음과 같습니다:

• 12 / 1 == 12
• 12 / 2 == 6
• 12 / 3 == 4

즉, i와 n / i가 약수 쌍을 이룹니다.

따라서, 1부터 sqrt(n)까지만 반복해도 모든 약수를 구할 수 있습니다. 이를 코드로 구현하면 다음과 같습니다:

for (int i = 1; i <= (int)Math.sqrt(n); i++)

 

주의할 점: 제곱근이 약수일 때, 예를 들어 n이 9일 경우 약수는 1, 3, 9입니다.

이 때, 제곱근인 3을 중복해서 더하지 않도록 주의해야 합니다.

테스트 케이스로 n이 9인 경우를 테스트하면 1 + 3 + 9 = 13이 되어야 합니다.

 

 

---

정답은 더보기 클릭

1. 1부터 n까지 반복하는 for문

class Solution {
    public int solution(int n) {
        // 정답을 저장하는 변수
        int result = 0;
        
        // 1~n까지 반복하는 for문
        for (int i = 1; i <= n; i++) {
            // 약수를 구하는 조건
            if (n % i == 0) {
                result += i;  // 약수를 result에 더하기
            }
        }
        return result;
    }
}

 

2. 1부터 n의 제곱근까지 반복하는 for문

class Solution {
    public int solution(int n) {
        int result = 0; // 약수의 합을 저장할 변수
        
        // 1부터 n의 제곱근까지 반복
        for (int i = 1; i <= (int) Math.sqrt(n); i++) {
            // n이 i로 나누어 떨어지는지 확인
            if (n % i == 0) {
                // i가 n의 제곱근이 아닌 경우, 두 약수를 더함
                if (n / i != i) {
                    result += n / i + i;
                } else { // i가 n의 제곱근인 경우, 중복된 약수를 한 번만 더함
                    result += i;
                }
            }
        }
        return result; // 최종 약수의 합 반환
    }
}