약수의 개수와 덧셈

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

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

문제 설명

두 정수 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 해야 합니다.

 

문제 해결

1. 약수의 개수를 찾는다.

2. 홀수 인지 짝수인지 구별

3. 짝수면 더하고 홀수면 뺀다

 

약수의 개수를 찾기 위해 isSquare 함수를 만듦

public boolean isSquare(int num){
    int cnt = 0;
    for(int i = 1 ; i<=num ; i++){
        if(num % i ==0) cnt++;
    }
    return (cnt % 2 == 0) ? false : true;
}

약수의 개수가 짝수인지 홀수인지 구분하여 return 해줌

약수의 개수를 찾는 알고리즘은 더 간편한게 있겠지만,

1 <= left <= right <= 1000 이라는 제한사항으로 봤을 때 시간이 오래걸리지 않을 것 같아 이렇게 짰다.

 

 

전체코드

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        
        for(int i = left; i <= right; i++){
            if(isSquare(i)){
                answer-=i;
                // System.out.println("제곱수 입니다 " +  i);
                // System.out.println("answer = " +  answer);
            }else{
                
                answer+=i;
                // System.out.println("제곱수 아님 " + i);
                // System.out.println("answer = " +  answer);
            }
        }
        
        return answer;
    }
    
    public boolean isSquare(int num){
        int cnt = 0;
        for(int i = 1 ; i<=num ; i++){
            if(num % i ==0) cnt++;
        }
        return (cnt % 2 == 0) ? false : true;
    }
}

 

약수 세는 함수 변경

public boolean isSquare(int num){
    int i = 1;
    while(i*i<=num){
        if(i*i == num) return true;;
        i++;
    }
    return false;
}

약수의 개수가 홀수인 것은 결국 제곱수 이므로

제곱수인지 아닌지 체크하면 시간을 크게 줄일 수 있다.