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

문제 출처 - Programmers

문제는 여기

코딩테스트 연습 - 약수의 개수와 덧셈

---

[풀이]

1. 1부터 j * j가 i일 때까지 j를 증가시키면서 반복한다.

2. 만약 j * j가 i라면 홀수갯수이므로 odd를 true로 바꿔준다.

3. odd가 true라면 값을 빼주고, 아니라면 더해준다.

4. 위 과정들을 left부터 right까지 반복한다.

5. 결과를 출력한다.

[접근]

1. 약수의 갯수가 홀수가 되려면 언제일까를 생각했을 때, 4, 9처럼 어떤 수의 제곱이 되면 홀수가 되는 것을 확인하고 이를 사용해 문제를 해결하였다.

[코드]

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        
        // left부터 right까지
        for (int i = left; i <= right; i++) {
            // 홀수인지 체크
            boolean odd = false;
            
            // 제곱근이 약수가 되면 홀수            
            // 1부터 제곱이 i 까지 체크
            for (int j = 1; j * j <= i; j++) {
                // 제곱이 i라면
                if (j * j == i) {
                    // 홀수
                    odd = true;
                    break;
                }
            }
            
            // 홀수가 아니면 +, 홀수면 -
            if (!odd)
                answer += i;
            else
                answer -= i;
        }
        
        return answer;
    }
}