[프로그래머스 / JAVA] Level 1 약수의 개수와 덧셈 (77884)

⏰ 2021-12-15 (수) 21:29:31

screener
시리즈 모아보기
프로그래머스

19 / 78

Table of Contents

  • 1. 약수의 개수와 덧셈







약수의 개수와 덧셈

랭크사용 언어
Level 1
JAVA

🔗 🔗 약수의 개수와 덧셈

문제 설명

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

제한사항

  • 1 ≤ leftright ≤ 1,000

입출력 예

leftrightresult
131743
242752

입출력 예 설명

입출력 예 #1

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

약수약수의 개수
131, 132
141, 2, 7, 144
151, 3, 5, 154
161, 2, 4, 8, 165
171, 172

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

입출력 예 #2

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

약수약수의 개수
241, 2, 3, 4, 6, 8, 12, 248
251, 5, 253
261, 2, 13, 264
271, 3, 9, 274

따라서, 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 ]을 가진다. 16=4\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();
	}
}

🏷️ 태그
# 프로그래머스
# 알고리즘
# JAVA(자바)
# Level 1

읽어주셔서 고마워요!

도움이 되셨다면, 공감이나 댓글을 달아주시는 건 어떤가요?

블로그 운영에 큰 힘이 됩니다.

https://hits.seeyoufarm.com/api/count/incr/badge.svg?count_bg=%23484848&icon=react.svg&icon_color=dodgerblue&title=view&title_bg=%23242424&url=https%3A%2F%2Fblog.itcode.dev%2Fposts%2F2021%2F12%2F15%2Fprogrammers-a0019