[2021-05-25] 약수의 개수와 덧셈

푼 시간 : 40분

언어 : 자바

 

---

 

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

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

 

재귀함수로 풀다보니 시간이 오래걸렸다

지저분한데 급해서 그냥 풀었다.

 

막상 남들 푼걸 보니 재귀가 없어도 되는 문제였다...

너무 어렵게 생각하려는 습관이 문제인 것 같다.

후배들 보면서도 하는 생각인데 나도 결국

똑같이 어렵게 연산하는길을 택하는경우가 많은 것 같다..

 

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        int[] count=new int[right-left+1];
        int temp=left;
        int sum;
        // 재귀함수에 넣을 약수 개수의 합
        int count_sum;
        // 재귀함수에 넣을 약수 카운터
        
        for(int i=0; i<count.length; i++){
            count_sum=1;
            // 약수는 1부터
            sum=0;
            count[i]=cal(left+i, sum, count_sum);
            // 약수 개수를 넣을 카운트, cal함수로 숫자하나당 재귀함수를 연출시킴
        }
        
        for(int i=0; i<count.length; i++){
            if(count[i]%2==1){
                answer+=temp;
                temp++;
                // 짝수면 더하기(count[i]가 0부터라서)
            }
            else{
                answer-=temp;
                // 홀수면 빼기
                temp++;
            }
        }
        
        return answer;
    }
    
    public int cal(int n,int sum, int count){
        if(n==count)
        // count가 left의 값과 같아지면 끝낸다.
            return sum;
        else if(n%count==0)
        // 카운트가 n(left)의 값의 약수일경우 sum을 더하며 리턴
            return cal(n, ++sum, ++count);
        else
        // 약수가 아닐경우 그냥 더한다.
            return cal(n, sum, ++count);
    }
}