[프로그래머스] 77884 약수의 개수와 덧셈 - Java

📌 문제 정보

• 출처: 문제 링크
• 난이도: ⭐
• 문제 유형: 수학
• 사용 언어: Java

---

🔍 문제 설명

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

 

제한사항

• 1 ≤ left ≤ right ≤ 1,000

---

💡 풀이 노트

💡 약수란 어떤 수를 나누었을 때 나머지가 0이 되는 수
즉, 어떤 수 `n`의 약수는 `n % i == 0`인 모든 정수 i로 이루어진 집합
예를 들어,
`6`의 약수: 1, 2, 3, 6 → 총 4개
`9`의 약수: 1, 3, 9 → 총 3개
`16`의 약수: 1, 2, 4, 8, 16 → 총 5개

👉 특징: 모든 자연수는 최소한 `1`과 `자기 자신`을 약수로 가짐

 

풀이

• `left`부터 `right`까지 반복문으로 순회
• 각 숫자에 대해 약수의 개수를 구함
• 약수의 개수가 짝수면 해당 수를 더하고, 홀수면 빼기를 수행합

주의

처음엔 약수를 구할 때 한번의 for문 반복이라도 줄이기 위해 아래와 같이 작성

for (int j = 2; j < i; j++)

이렇게 하면 `1`과 `자기 자신`은 약수에서 제외되기 때문에 정확한 약수 개수를 구할 수 없다.

특히 left~right 범위에 1이 포함되는 경우, 약수 개수가 잘못 계산되어 잘못된 결과가 나옴.

→ 테스트케이스1번이 틀린다면 범위 설정의 문제

---

🚀 코드 (Java)

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        for(int i = left; i <= right ; i++){
            int cnt = 0 ; //i의 약수 개수
            for(int j = 1 ; j<= i ; j++)
                if(i%j == 0) cnt++; // 나머지가 0이면 약수
					  
	// 약수 개수에 따라 더하거나 뺴기
            if(cnt %2 ==0) answer += i;
            else answer -= i;
        }
        return answer;
    }
}

---

🖥 실행 결과

입력 & 출력

left	right	result
13	17	43
24	27	52

---

🔄 개선 가능성

• 약수의 개수가 홀수 → 제곱근으로 나누면 0으로 나누어떨어진다.
  ex) 9의 약수 : [1, 3, 9] , 16의 약수: [1, 2, 4, 8, 16]

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;
                continue;
            }
            answer += i;
        }
        return answer;
    }
}

---

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest