[Java&알고리즘] 약수의 개수와 덧셈 (Level 1)

 

프로그래머스의 알고리즘 문제 및 풀이에 대해 차근차근 포스팅하려합니다.

 

저도 초보자이기도하고 알고리즘에 쉽게 다가갈 수 없는 부분들이 많기 때문에

최대한 알기 쉽게 정리해보려하고 알고리즘을 어려워하는 분들에게 도움이 되었으면 합니다.

 

많이 공유되고 토론이 될 수 있는 공간이 되었으면 좋겠습니다.

 

 

 

 

 

 

 

 

환경

언어 : 자바

단계 : 레벨 1단계 (입문자용)

정답률 : 80%

 

 

 

 

 

 

제목 

 

약수의 개수와 덧셈

 

 

 

 

 

 

문제 설명 및 코드

 

 

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

 

 

 

제한 조건

 

 - 1 ≤ left ≤ right ≤ 1,000

 

 

 

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
 
        return answer;
    }
}

 

 

 

 

 

입출력 예

 

 

left	right	return
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 a=left; a<=right; a++){
            int chk = 0;
            for(int s=1; s<=a; s++){
                chk += (a%s==0) ? 1 : 0;  
            }
            answer += (chk%2==0) ? a : -a;
        }
        return answer;
    }
}

 

저는 이중 반복문을 통해서 해결해보았습니다..

 

chk 변수를 두고,

 

첫번째 반복문이 돌때마다 두번째 반복문에서 나누어 떨어지는 수가

 

짝수라면 1을 더해주고 아니면 0을 반환해줍니다.

 

그리고 두번째 반복문을 나와서 반환 변수 answer에 chk 변수를 조건하여

 

나누어 떨어지면 양수, 아니면 음수를 answer변수에 더해주기만 하면 됩니다.

 

 

 

 

 

 

 

 

다른사람 풀이

 

 

 

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
 
        for (int i=left;i<=right;i++) {
            //제곱수인 경우 약수의 개수가 홀수
            if (i % Math.sqrt(i) == 0) {
                answer -= i;
            }
            //제곱수가 아닌 경우 약수의 개수가 짝수
            else {
                answer += i;
            }
        }
 
        return answer;
    }
}
 

 

 

Math.sqrt 메서드를 통해 제곱수를 구하고 

 

제곱수인 경우 약수의 갯수가 홀수로하여 빼주고,

 

제곱수가 아닌 경우 약수의 갯수가 짝수로하여 더해주는 방식입니다.

 

제곱수로 약수를 알아내는 것 자체가 신선하네요...