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

약수의 개수와 덧셈

문제 설명

두 정수 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;

        for(int i=left; i<=right; i++){
            int count = 0;

            for(int j=1; j<=i; j++){
                if(i%j==0){
                    count++;
                }
            }

            if(count%2==0){
                answer += i;
            }else{
                answer -= i;
            }
        }

        return answer;
    }
}

해설

2중 for문을 사용해서 1번째 for문은 left숫자부터 right까지, 2번째 for문은 1부터 left의 값까지 반복하여 약수를 찾는다. 약수의 개수를 count 하여 count값이 짝수면 더해주고 홀수면 마이너스해준다.

 

여러 가지의 풀이를 보고 비교해보던 중, 인상 깊은 코드가 있었다.

Math클래스의 sqrt 메서드를 통해서 간단하게 구현한 경우이다.

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

만약 left : 16, right : 18 인 경우 

Math.sqrt(15) : 3.872983346207417 - 3 = 0.001 이상

약수 : 1, 3, 5, 15

 

Math.sqrt(16) : 4.0 - 4 = 0.001 미만

약수 : 1, 4, 16

 

Math.sqrt(17) : 4.123105625617661 - 4 = 0.001 이상

약수 : 1, 17

 

즉, sqrt메서드로 제곱근을 구해서 (int) 형 제곱근을 뺄셈을 해주는데, 16처럼 약수의 개수가 홀수인 경우엔 제곱근이 정수로 딱 떨어지게 된다. 약수의 개수가 홀수인 경우엔 sqrt - (int) sqrt의 수가 0.001보다 이상인 경우이다.

 

출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/77884