[프로그래머스] 약수의 개수와 덧셈 제곱근방식

문제

주어진 정수 left ~ right까지의 모든 수들의 약수의 갯수를 구하고, 약수의 갯수가 짝수면 answer 에 더하고 홀수면 answer에서 뺀 최종 결과값을 구하시오.

접근

제곱근 방식을 사용해 반복 횟수를 최소화하여 작업하도록 작성함.

우선 각 숫자별 약수의 갯수를 구한 후, 갯수에 따라 answer에서 증감시킨다.

public static int solution(int left, int right) {
        List<Integer> factors = new ArrayList<>();
        List<Integer> numbers = new ArrayList<>();

        int answer = 0;
        //각 숫자별 약수의 갯수 구하기 제곱근 방식
        for(int i = left; i <= right; i ++){
            int cnt = 0;
            for(int j = 1; j <= Math.sqrt(i); j ++){
                if (i % j == 0) {
                    cnt ++;
                    if( j != i / j) {
                        cnt ++;
                    }
                }
            }
            factors.add(cnt);
            numbers.add(i);
        }

        for(int i = 0 ; i < factors.size(); i++){
            if( factors.get(i) % 2 == 0) {
                answer += numbers.get(i);
            } else {
                answer -= numbers.get(i);
            }
        }

        return answer;
    }