프로그래머스 - 약수의 합 java :: 12928

문제 링크

코딩테스트 연습 - 약수의 합 | 프로그래머스 (programmers.co.kr)

---

문제 풀이

1번 풀이

• 약수를 구하는 방법
  어떤 수를 나눈 나머지가 0인 경우 약수

public int solution(int n) {
    int sum = n;
    for (int i = 1; i <= n / 2; i++) {
        if (n % i == 0) sum += i;
    }

    return sum;
}

테스트 처리속도

테스트	속도
테스트 1 〉	통과 (0.02ms, 73.6MB)
테스트 2 〉	통과 (0.01ms, 78MB)
테스트 3 〉	통과 (0.05ms, 81.7MB)
테스트 4 〉	통과 (0.02ms, 75MB)
테스트 5 〉	통과 (0.04ms, 76.5MB)
테스트 6 〉	통과 (0.03ms, 71.5MB)
테스트 7 〉	통과 (0.04ms, 72MB)
테스트 8 〉	통과 (0.03ms, 72MB)
테스트 9 〉	통과 (0.03ms, 73.5MB)
테스트 10 〉	통과 (0.06ms, 70.5MB)
테스트 11 〉	통과 (0.03ms, 72.6MB)
테스트 12 〉	통과 (0.06ms, 68.3MB)
테스트 13 〉	통과 (0.01ms, 72.9MB)
테스트 14 〉	통과 (0.04ms, 72.9MB)
테스트 15 〉	통과 (0.03ms, 72MB)
테스트 16 〉	통과 (0.02ms, 76.8MB)
테스트 17 〉	통과 (0.04ms, 73.3MB)

2번 풀이

• 자기 자신을 제외한 모든 약수는 자신의 절반 이하이다.
  예) 12의 약수는 {1, 2, 3, 4, 6, 12}
  자기 자신인 12를 제외한 모든 약수는 12의 절반인 6 이하이다.
  이를 활용해 구하고자 하는 값의 수행속도를 줄일 수 있다.

import java.util.HashSet;

public int solution(int n) {
    HashSet<Integer> set = new HashSet<Integer>();
    for(int i=1; i<=Math.sqrt(n); i++) {
        if(n % i == 0) {
            set.add(i);
            set.add(n / i);
        }
    }

    return set.stream().mapToInt(Integer::intValue).sum();
}

• 모든 약수는 짝이 있으며 그 짝의 작은 값은 자신의 제곱근을 초과할 수 없다.
  • 예) 16의 제곱근은 4 / 16의 약수는 {1, 2, 4, 8, 16}
    짝 : 1 - 16
    짝 : 2 - 8
    짝 : 4 - 4
  • 즉, 약수의 합을 구하기 위해서는 제곱근 이하의 값(1, 2, 4)만 구하면 되고 해당 값을 구하면 나머지(16, 8, 4)를 구할 수 있다.
    16 / 1 = 16
    16 / 2 = 8
    16 / 4 = 4
  • HashSet을 사용한 이유는 중복을 제거하기 위해서 사용했다. (예를 들어 16의 약수 중 4)

테스트 처리속도

테스트	속도
테스트 1 〉	통과 (2.20ms, 79.1MB)
테스트 2 〉	통과 (2.40ms, 83.2MB)
테스트 3 〉	통과 (1.65ms, 76.5MB)
테스트 4 〉	통과 (1.49ms, 80.6MB)
테스트 5 〉	통과 (1.48ms, 79.5MB)
테스트 6 〉	통과 (1.38ms, 70.2MB)
테스트 7 〉	통과 (1.54ms, 71.8MB)
테스트 8 〉	통과 (1.55ms, 76.2MB)
테스트 9 〉	통과 (2.52ms, 85.4MB)
테스트 10 〉	통과 (2.34ms, 72.1MB)
테스트 11 〉	통과 (1.21ms, 74.8MB)
테스트 12 〉	통과 (1.59ms, 82.9MB)
테스트 13 〉	통과 (2.13ms, 83MB)
테스트 14 〉	통과 (1.41ms, 71.1MB)
테스트 15 〉	통과 (3.55ms, 73.7MB)
테스트 16 〉	통과 (1.59ms, 82MB)
테스트 17 〉	통과 (1.42ms, 74.5MB)

문제풀이별 수행속도 차이

빠르게 구할 수 있는 작은 수의 값에 1번 풀이는 빠른 속도가 나오지만 크고 복잡한 수에서는 급격하게 느려진다.

2번 풀이는 매번 비슷한 수행속도를 보인다.

문제에서 주어진 것처럼 3000 이하의 자연수라면 1번 풀이로 푸는 것이 좋겠으나

주어진 값의 범위가 크다면 2번 풀이로 푸는 것이 좋을 것 같습니다.

---