[프로그래머스] 약수의 개수와 덧셈

문제 링크 : 링크텍스트

내 코드

public int solution(int left, int right) {
        int answer = 0;
        for(int i = left; i <= right; i++){
            Double sqrt = Math.sqrt(i);
            if(sqrt == sqrt.intValue()){
                answer -= i;
            }else{
                answer += i;
            }
        }
        return answer;
    }

문제를 처음 봤을 때 약수의 개수를 어떻게 구하는지에 대해 고민이 있었다.
n의 약수를 구한다고 가정하면 일일히 1부터 n까지 나눠봐서 나머지가 0인 숫자의 개수를 구하는 방법, 소인수분해를 해서 지수에 1을 더한 값끼리 곱하는 방법 처음에는 두가지가 생각났다.

하지만 두 방법 모두 시간복잡도가 너무 높게 책정될 것 같아 다른 방법을 생각해봤다.

우리가 구해야 하는 것에 집중해봤는데, 약수가 '홀수'인지 '짝수' 인지 구하고자 하는 것이지, 전체 약수의 개수를 구해야 할 필요가 없다는 것을 생각했다.
약수의 개수가 홀수인 경우는 정수 제곱근이 존재한다는 것이고, 짝수인 경우는 정수 제곱근이 존재하지 않는다는 뜻이다.

이 방식대로 제곱근을 구해서 제곱근의 정수값과 원래 제곱근의 값이 같으면 약수의 개수가 홀수인 경우이므로 값을 빼줬고, 그렇지 않다면 약수의 개수가 짝수이므로 값을 더해줬다.