코딩테스트 연습 > 월간 코드 챌린지 시즌2 > 약수의 개수와 덧셈 (제곱근 Math.sqrt)

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/77884

프로그래머스

 

 

풀이 - 나의 생각

1. 먼저, 1부터 주어진 수의 제곱근까지의 범위에서 반복합니다. 이 범위를 선택하는 이유는 주어진 수의 약수는 해당 수의 제곱근보다 클 수 없기 때문입니다. 만약 제곱근보다 큰 약수가 존재한다면, 해당 약수는 이미 이전에 제곱근 이하의 약수에서 포함되었을 것입니다.
2. 주어진 수를 반복하는 동안, 해당 수를 현재 인덱스로 나누어떨어지는지 확인합니다. 나누어떨어지면 현재 인덱스는 해당 수의 약수이므로 카운트를 증가시킵니다.
3. 만약 나누어떨어진 수가 현재 인덱스와 같다면, 이는 제곱수임을 의미합니다. 예를 들어, 99의 약수 중 33은 제곱근인 √9​=3과 같으므로 제곱수입니다. 따라서 카운트를 증가시킵니다.
4. 그렇지 않은 경우에는 현재 인덱스와 나누어떨어진 수의 약수가 모두 카운트에 포함되므로, 카운트를 2 증가시킵니다.
5. 반복이 완료되면 약수의 총 개수를 반환합니다.

예를 들어,n=12인 경우

1. i=1일 때, 12를 1로 나누면 나누어떨어지므로 약수이며, 카운트는 +2 증가합니다.
2. i=2일 때, 12를 2로 나누면 나누어떨어지므로 약수이며, 카운트는 +2 증가합니다.
3. i=3일 때, 12를 3으로 나누면 나누어떨어지므로 약수이며, 카운트는 +2 증가합니다.

이렇게 하여 12의 약수의 개수는 6이 됩니다.

 

예를 들어,n=16인 경우

1. i=1일 때, 12를 1로 나누면 나누어떨어지므로 약수이며, 카운트는 +2 증가합니다.
2. i=2일 때, 12를 2로 나누면 나누어떨어지므로 약수이며, 카운트는 +2 증가합니다.
3. i=3일 때, 12를 3으로 나누면 나누어떨어지지 않으므로 약수가 아닙니다.
4. i=4일 때, 12를 4으로 나누면 나누어떨어지고 제곱근이므로, 카운트는 +1 증가합니다.

이렇게 하여 12의 약수의 개수는 5이 됩니다.

 

 

 

코드

 

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        for(int i = left; i <= right; i++){
            if(flag(i)%2 == 0){
                answer+=i;
            }else{
                answer-=i;
            }
        }
        return answer;
    }
    
    public int flag(int n){
        int count = 0;
        for(int i = 1; i <= Math.sqrt(n); i++){
            if (n % i == 0) {
                if (n / i == i) { // 제곱수인 경우
                    count++;
                } else { // 제곱수가 아닌 경우
                    count += 2;
                }
            }
        }
        
        return count;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요