[프로그래머스/Day 2] 약수의 합을 구현하는 3가지 방법

1-1. 약수의 개념만 알고 구현하기

• 어떤 수 i로 n을 나눴을 때 나머지가 0이면 i는 n의 약수이다.

이 개념만 알고 있을 때 가능한 구현이 1부터 n까지 전부 나눠서 딱 떨어지는지 확인하는 것이다.

int solution(int n) {
    int answer = 0;

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

    return answer;
}

• 이 방법은 개념을 이해하기에 좋지만, n이 커지면 굉장히 느려진다.

1-2. 약수의 특징도 알고 구현하기: 약수 목록을 실제로 찾아서 더하는 방식

• 작은 숫자의 약수 예시를 보면 12의 경우,
  • (1, 12), (2, 6), (3, 4) 와 같이 약수는 항상 짝으로 구성된다.
• 이러한 관찰을 통해 알 수 있는 점은:
  • 작은 쪽 약수는 √n 이하에만 존재한다.
  • 큰 쪽 약수는 작은 쪽의 "짝"으로 자동을 따라온다.
  • → 1부터 √n 까지만 검사해도 모든 약수를 다 찾을 수 있다.

long long solution(int n)
{
    long long ans = 0;
    for (long long d = 1; d * d <= n; ++d)
    {
        if (n % d) continue; // 딱 안 나눠떨어지면 스킵

        long long q = n / d; // 짝 약수
        ans += d;            // 작은 약수 더하고
        if(q != d) ans += q; // 짝 약수도 더함
    }

    return ans;
}

• for문은 종료 조건이 i * i <= n 형태를 가질 때,
  O(√n)의 시간복잡도가 된다.
• 최대 √n까지만 돌기 때문에 엄청 빨라진다. 하지만 여전히 n이 아주 크면 √n도 부담일 수 있다.

1-3 소인수분해로 약수의 합 공식을 만들어 구현하기: 약수들의 합을 한 번에 계산하는 방식

long long solution(int n) {
    if (n <= 1) return n;

    long long ans = 1;
    int x = n;

    // 1) 소인수분해 (2부터 루트 x까지)
    for (long long p = 2; p * p <= x; ++p)
    {
        if (x % p != 0) continue;

        int a = 0;
        while (x % p == 0)
        {
            x /= (int)p;
            ++a;
        }

        // 2) 각 소수별 등비합 작성: 1 + p + ... + p^a
        long long term = 1;
        long long pk = 1;
        for (int i = 0; i < a; ++i)
        {
            pk *= p;
            term += pk;
        }

        // 3) 전부 곱
        ans *= term;
    }

    // 남은 소수가 있으면 지수 1
    if (x > 1)
    {
        ans *= (1LL + x);
    }

    return ans;
}