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

문제 설명
정수 n이 주어졌을 때, n의 모든 약수를 더한 값을 반환하는 함수를 작성하는 문제입니다. 예를 들어, n = 12라면 약수는 1, 2, 3, 4, 6, 12이고, 이들의 합은 28입니다.

---

제한 사항

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

---

입출력 예

n	return
12	28
5	6

• 입출력 예 #1: 12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다.
• 입출력 예 #2: 5의 약수는 1, 5입니다. 이를 모두 더하면 6입니다.

---

문제 풀이

이 문제는 주어진 n의 약수를 구하고, 그 합을 반환하는 문제입니다. 앞서 설명한 것처럼, 약수는 대칭적으로 존재하기 때문에 모든 약수를 구하기 위해서는 1부터 √n까지만 확인하면 됩니다. 다만, n이 0일 경우 약수가 없기 때문에, 0에 대해서는 특별 처리가 필요합니다.

1. Python 코드 풀이

def solution(n):
    if n == 0:
        return 0

    total = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            total += i
            if i != n // i:  # 중복된 약수가 아니면 더함
                total += n // i
    return total

# 테스트 예시
print(solution(12))  # 출력: 28
print(solution(5))   # 출력: 6

코드 설명

• n == 0인 경우에는 약수가 없으므로 0을 반환합니다.
• 그 외의 경우에는 1부터 √n까지 반복하면서 n의 약수를 찾습니다.
• n % i == 0이면, i와 n // i는 모두 n의 약수이므로 합에 더합니다. 단, i가 n // i와 같으면 중복된 값이므로 한 번만 더합니다.

---

2. Java 코드 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;  // 약수의 합을 저장할 변수

        // 1부터 i*i <= n까지 반복
        for(int i = 1; i*i <= n; i++){
            if(n % i == 0){  // i가 n의 약수인지 확인
                answer += i;  // i가 약수이면 i를 더함

                // i와 n / i가 다른 경우에만 추가로 n / i를 더함 (중복 방지)
                if(i != n / i ){
                    answer +=  n / i;
                }
            }
        }

        return answer;  // 모든 약수를 더한 결과를 반환
    }
}

코드 설명

이 코드의 목적은 주어진 정수 n의 약수의 합을 구하는 것입니다. 약수는 어떤 수를 나누었을 때 나머지가 0인 수를 말합니다. 이 코드는 약수의 성질을 이용하여 시간 복잡도를 효율적으로 줄이는 방식으로 작성되었습니다. 자세히 살펴보겠습니다.

코드 구조 및 설명

1. 변수 초기화

int answer = 0;

• 약수의 합을 저장할 변수 answer를 0으로 초기화합니다. 이 변수는 최종적으로 약수들을 모두 더한 값을 반환합니다.

2. 반복문: 약수 탐색

for(int i = 1; i * i <= n; i++){

• 반복문은 i = 1부터 시작하여 i * i <= n 조건이 만족될 때까지 실행됩니다. 즉, i가 n의 제곱근 이하일 때만 반복됩니다.
  • 약수는 대칭적으로 존재합니다. 예를 들어, n = 36일 경우 (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)처럼 나타나므로 n의 제곱근까지만 확인하면 나머지 큰 약수는 자동으로 구할 수 있습니다.
  • 이 때문에 i가 √n 이하일 때까지만 반복문을 실행하여 시간을 절약할 수 있습니다.

3. 약수 확인

if(n % i == 0){

• n % i == 0 조건은 n을 i로 나누었을 때 나머지가 0인지, 즉 i가 n의 약수인지를 확인하는 조건입니다.
  • 만약 n % i == 0이면 i는 n의 약수입니다.

4. 약수 더하기

answer += i;

• i가 약수로 확인되면, 이를 answer에 더합니다.

5. 대칭 약수 더하기 (중복 방지)

if(i != n / i ){
    answer += n / i;
}

• 이 조건은 i와 n / i가 서로 다른 경우에만 n / i도 answer에 더하는 부분입니다.
  • 예를 들어, n = 36일 때, i = 2이면 n / i = 18이므로 2와 18을 동시에 더해야 합니다.
  • 하지만 i = 6일 때는 n / i도 6이므로 이 값은 한 번만 더해야 합니다. 즉, i와 n / i가 같은 경우에는 중복을 방지하기 위해 한 번만 더해줍니다.

6. 결과 반환

return answer;

• 모든 약수를 더한 후 answer를 반환합니다.

작동 원리 예시

• 예를 들어, n = 36일 때:

  • i = 1 → 1은 36의 약수, answer += 1 → 대칭 약수 36도 더함 → answer += 36 (answer = 37)
  • i = 2 → 2는 36의 약수, answer += 2 → 대칭 약수 18도 더함 → answer += 18 (answer = 57)
  • i = 3 → 3은 36의 약수, answer += 3 → 대칭 약수 12도 더함 → answer += 12 (answer = 72)
  • i = 4 → 4는 36의 약수, answer += 4 → 대칭 약수 9도 더함 → answer += 9 (answer = 85)
  • i = 6 → 6은 36의 약수, answer += 6 → 6과 6이 동일하므로 한 번만 더함 (answer = 91)
  • 이후 i가 √36 = 6을 넘으므로 반복문 종료.

• 결과: 36의 모든 약수(1, 2, 3, 4, 6, 9, 12, 18, 36)를 더한 값인 91을 반환합니다.

시간 복잡도 분석

• 반복문은 1부터 √n까지 실행되므로 시간 복잡도는 O(√n)입니다.
• 이 코드는 n이 최대 3000까지 가능하므로 매우 효율적입니다.

결론

이 문제는 약수를 구하는 전형적인 문제로, 약수의 대칭성을 이용하면 시간 복잡도를 O(√n)으로 최적화할 수 있습니다. 이를 통해 제한 조건 내에서 매우 효율적으로 문제를 해결할 수 있습니다.