[코테/JAVA] 월간 코드 챌린지 시즌2 : 약수의 개수와 덧셈

2021.11.06

66번째 포스팅

 

입사 244일차.

코테 문제풀이 5주차 1번 문제

 

 

0. 문제

  ① 월간 코드 챌린지 시즌2 : 약수의 개수와 덧셈

  ② 설명

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

  ③ 링크

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

 

 

1. 접근방법

  생각해낸 방법은 1가지

  ① 문제에서 설명한 그대로 풂

 

 

2. 풀이

  ① 접근방법 : ①

  ② 풀이

class Solution {
    /*
    * 시작시간 : 20:50 
    * 종료시간 : 21:14
    */
    public int solution(int left, int right) {
        int answer = 0;
        for (int i = left; i <= right; i++) {
            answer += calDivisor(i);
        }
        return answer;
    }
    
    public int calDivisor(int n) {
        // 1. 제곱근 찾기
        int squareRoot = (int)Math.floor(Math.sqrt(n));
        
        // 2. 약수의 갯수 찾기
        int divisorCnt = 0;
        for (int i = 2; i <= squareRoot; i++) {
            if (n % i == 0) divisorCnt++;
        }
        // 3. 제곱근까지 for문을 돌렸으므로 *2
        divisorCnt *= 2;
        
        // 4. 제곱수일 경우 -1
        if (Math.sqrt((double)n) == (double)squareRoot) {
            divisorCnt--;
        }
        
        int answer = 0;
        if (divisorCnt % 2 != 0) {
            n *= -1;
        }
        answer = n;
    
        return answer;
    }
}

 

 

3. 결과

 

 

4. 주의사항

  ① 제곱근까지 for문을 사용해서 약수의 갯수를 구해 시간복잡도를 줄일 것

  ② 제곱수인지 아닌지에 대한 판별