약수의 합

문제 설명

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

제한 사항

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

입출력 예

n	return
12	28
5	6

풀이 과정

1단계 - 기본 풀이 O(n)

처음에는 1부터 n까지 순회하며 약수를 찾는 방식으로 접근했다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=1; i<=n; i++){
            if(n%i==0){
                answer += i;
            }
        }
        
        return answer;
    }
}

2단계 - 최적화 풀이 O(√n)

핵심 아이디어

약수는 항상 쌍으로 존재한다.

n = 12
1 × 12
2 × 6
3 × 4

약수 쌍에서 작은 쪽은 반드시 √n 이하에 존재한다.
→ √n 까지만 순회해도 모든 약수를 찾을 수 있다!

예외 케이스 - 완전제곱수

n = 9, i = 3
3 × 3 = 9  →  쌍이 같은 수!
→ 한 번만 더해야 한다

int 나눗셈 함정

n = 5, i = 2
5 / 2 = 2  (2.5가 아님!)
→ 가짜 약수 쌍이 생길 수 있음
→ n % i == 0 으로 먼저 약수 여부 확인 필요!

최종 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=1; i<=Math.sqrt(n); i++){
            if(n % i == 0){
                if(i != (n/i)){
                    answer += i + (n/i);
                } else {
                    answer += i;
                }
            }
        }
        
        return answer;
    }
}

성능 비교

방식	반복 횟수 (n=3000)	시간복잡도
기본 풀이	3000번	O(n)
최적화 풀이	약 55번	O(√n)

핵심 정리

약수는 쌍으로 존재
    → 한쪽은 반드시 √n 이하
        → √n 까지만 순회해도 충분
            → 단, 완전제곱수 예외처리!
            → int 나눗셈 함정 주의!