[Java] 약수의 개수와 덧셈 (programmers)

0830

---

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ left ≤ right ≤ 1,000

입출력 예

left	right	result
13	17	43
24	27	52

입출력 예 설명

입출력 예 #1

• 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.

수	약수	약수의 개수
13	1, 13	2
14	1, 2, 7, 14	4
15	1, 3, 5, 15	4
16	1, 2, 4, 8, 16	5
17	1, 17	2

• 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.

입출력 예 #2

• 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.

수	약수	약수의 개수
24	1, 2, 3, 4, 6, 8, 12, 24	8
25	1, 5, 25	3
26	1, 2, 13, 26	4
27	1, 3, 9, 27	4

• 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

소스 코드

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        int cnt = 0;            //약수의 개수
        
        for ( int i = left; i <= right; i++ ) {
            for ( int j = 1; j <= i/2; j++) {       //약수 구하기
                if ( i % j == 0) cnt++;             //약수 개수 누적하기
            }
            answer += ( cnt % 2 == 0 )? -i : i;     //약수의 개수가 짝수면 더하고 반대
            cnt = 0;
        }
        return answer;
    }
}

소스 풀이

int answer = 0;			//약수의 개수가 짝수면 더한 값, 홀수면 뺀 값의 합계
int cnt = 0;            //약수의 개수

약수의 개수가 짝수면 더한 값, 홀수면 뺀 값의 합계를 나타내는 answer변수를 선언 및 초기화한다.
약수의 개수를 나타내는 cnt변수를 선언 및 초기화한다.

		for ( int i = left; i <= right; i++ ) {
            for ( int j = 1; j <= i/2; j++) {       //약수 구하기
                if ( i % j == 0) cnt++;             //약수 개수 누적하기
            }
            answer += ( cnt % 2 == 0 )? -i : i;     //약수의 개수가 짝수면 더하고 반대
            cnt = 0;
        }
        return answer;

변수 left의 값을 유지시키기 위해 새로운 변수인 i에 left의 값을 저장한다.
left부터 right까지 for문을 반복시키며 i++을 계속 반복해 i의 값이 right의 값보다 커지면 for문을 빠져나온다.

나눌 변수인 j의 초깃값을 1로 잡고 left값을 나타내는 i를 j로 나눈 나머지가 0이라면, 즉 j가 i의 약수라면 약수의 개수를 나타내는 변수인 cnt를 ++연산시킨다.
i/2까지 for문을 반복하는 이유는 더 적은 반복으로도 약수를 구하기에는 충분하기 때문이다.

i의 약수의 개수를 나타내는 cnt가 짝수이면 더하고 홀수이면 뺍니다.
cnt는 다시 0으로 초기화 시켜서 i++된 i의 약수의 개수를 새롭게 카운팅합니다.

구한 약수의 합계인 answer를 return합니다.

---