[Java] 프로그래머스 12928. 약수의 합 (Lv.1)

https://school.programmers.co.kr/learn/courses/30/lessons/12928

프로그래머스

 

입력 사이즈가 작아서 대충 돌려도 되지만... 약수의 특징을 사용하면 조금 더 효율적인 코드를 짤 수 있습니다.

N의 제곱근을 기준으로 작은 약수와 큰 약수로 나누어 두개를 동시에 찾으면 됩니다.

 

예를 들어 100의 약수를 찾을때, 100의 제곱근은 10입니다.

10보다 작은 100의 약수 1, 2, 4, 5는 각각 100, 50, 25, 20과 대응됩니다.

또 100의 제곱근인 10이 정수이므로 10도 포함할 수 있습니다. 이렇게 약수를 찾는 경우 N이 클 때는 어마어마한 시간차이가 나게 됩니다.

 

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