약수의 개수와 덧셈

---

🔗 🔗 약수의 개수와 덧셈

문제 설명

---

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

제한사항

---

• 1 ≤ left ≤ right ≤ 1,000

입출력 예

---

입출력 예 설명

---

입출력 예 #1

다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.

따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.

입출력 예 #2

다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.

따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

풀이

---

난이도가 낮은 간단한 문제. 약수를 구하는 알고리즘 정도만 구현하면 어렵지않게 풀 수 있다.

1. 약수를 구한다.
   • 약수를 알 필요는 없고, 갯수 정도만 있어도 무방하다.
2. 약수 갯수의 홀짝여부를 비교한다.
   1. 짝수일 경우 가산한다.
   2. 홀수일 경우 감산한다.
3. 누적한 값을 반환한다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private int[] measure(int num)
{
	ArrayList<Integer> list = new ArrayList<>();
	
	for (int i = 1; i <= Math.sqrt(num); i++)
	{
		// 임의의 수와 나누어 떨어질 경우
		if (num % i == 0)
		{
			list.add(i);
			
			// num의 제곱근값이 아닐 경우
			if (i * i != num)
			{
				list.add(num / i);
			}
		}
	}
	
	return list.stream().sorted().mapToInt(Integer::intValue).toArray();
}

약수를 구하는 알고리즘은 위와 같다. 약수를 구할 땐 대상의 제곱근까지만 확인해도 무방하다.

예를 들어, 16의 경우 [ 1, 2, 4, 8, 16 ]을 가진다. $\sqrt{16} = 4$이므로 4까지만 비교하여 [ 1, 2, 4 ]까지만 구해도 약수의 전체를 알 수 있다.

16은 16 / 1, 8은 16 / 2를 통해 유추할 수 있기 때문이다. i * i != num일 경우 num이 자신의 제곱근을 약수로 갖는 것으로, 다른 수와 달리 num과 나누지 않고 i 하나만 추가한다. 위 예시에선 4가 그 케이스다.

이후 약수의 갯수를 확인하여 홀짝 여부에 따라 값을 가감하면 된다.

코드

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.ArrayList;

/**
 * 약수의 개수와 덧셈 클래스
 *
 * @author RWB
 * @since 2021.12.12 Sun 00:33:56
 */
class Solution
{
	/**
	 * 해답 반환 메서드
	 *
	 * @param left: [int] 정수 1
	 * @param right: [int] 정수 2
	 *
	 * @return [int] 해답
	 */
	public int solution(int left, int right)
	{
		int answer = 0;
		
		for (int i = left; i <= right; i++)
		{
			int count = measure(i).length;
			
			answer += count % 2 == 0 ? i : -i;
		}
		
		return answer;
	}
	
	/**
	 * 약수 반환 메서드
	 *
	 * @param num: [int] 숫자
	 *
	 * @return [int[]] 약수
	 */
	private int[] measure(int num)
	{
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int i = 1; i <= Math.sqrt(num); i++)
		{
			// 임의의 수와 나누어 떨어질 경우
			if (num % i == 0)
			{
				list.add(i);
				
				// num의 제곱근값이 아닐 경우
				if (i * i != num)
				{
					list.add(num / i);
				}
			}
		}
		
		return list.stream().sorted().mapToInt(Integer::intValue).toArray();
	}
}