𝝅번째 알파카의 개발 낙서장

screen

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

posts

알고리즘

시리즈 톺아보기

프로그래머스

프로그래머스
count

약수의 개수와 덧셈 🔗

랭크 사용 언어
Level 1 JAVA

🔗 약수의 개수와 덧셈

문제 설명 🔗

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

제한사항 🔗

  • 1 ≤ leftright ≤ 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. 약수 갯수의 홀짝여부를 비교한다.
    1. 짝수일 경우 가산한다.
    2. 홀수일 경우 감산한다.
  3. 누적한 값을 반환한다.

JAVA

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

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

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

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


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

코드 🔗

JAVA

0import java.util.ArrayList;
1
2/**
3 * 약수의 개수와 덧셈 클래스
4 *
5 * @author RWB
6 * @since 2021.12.12 Sun 00:33:56
7 */
8class Solution
9{
10 /**
11 * 해답 반환 메서드
12 *
13 * @param left: [int] 정수 1
14 * @param right: [int] 정수 2
15 *
16 * @return [int] 해답
17 */
18 public int solution(int left, int right)
19 {
20 int answer = 0;
21
22 for (int i = left; i <= right; i++)
23 {
24 int count = measure(i).length;
25
26 answer += count % 2 == 0 ? i : -i;
27 }
28
29 return answer;
30 }
31
32 /**
33 * 약수 반환 메서드
34 *
35 * @param num: [int] 숫자
36 *
37 * @return [int[]] 약수
38 */
39 private int[] measure(int num)
40 {
41 ArrayList<Integer> list = new ArrayList<>();
42
43 for (int i = 1; i <= Math.sqrt(num); i++)
44 {
45 // 임의의 수와 나누어 떨어질 경우
46 if (num % i == 0)
47 {
48 list.add(i);
49
50 // num의 제곱근값이 아닐 경우
51 if (i * i != num)
52 {
53 list.add(num / i);
54 }
55 }
56 }
57
58 return list.stream().sorted().mapToInt(Integer::intValue).toArray();
59 }
60}