[프로그래머스_ Java_Lv1] 약수의 개수와 덧셈. 제곱수 판별 (sqrt)

public int solution(int left, int right) {
        int answer = 0;
        int count = 1;

        for (int i = left; i <= right; i++) {
            for (int j = 2; j <= i; j++) {
                if (i % j == 0) {
                    count++;
                }
            }
            if (count % 2 == 0) {
                answer += i;
            } else {
                answer -= i;
            }
            count = 1;
        }
        return answer;
    }

• 비효율적: 시간 복잡도는 O(N²) 수준 (right가 커질수록 매우 느려짐)

• 매번 약수를 모두 세야 함 → 특히 i가 클수록 반복 횟수가 많아짐

---

다른 풀이 (제곱수 판별)

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

• 제곱수인 경우 약수의 개수가 홀수이고 제곱수가 아닌 경우 약수의 개수가 짝수이다.

어떤 수의 약수는 항상 (a, b)처럼 쌍을 이루는데
예: 12 → (1,12), (2,6), (3,4) → 총 6개 (짝수)
그런데 제곱수는 (√n, √n)처럼 한 쌍이 겹침
예: 9 → (1,9), (3,3) → 3이 두 번 세어지지 않으므로 총 약수는 3개 (홀수)

즉,

• 제곱수면 약수 개수 홀수

• 제곱수가 아니면 약수 개수 짝수