[프로그래머스][코딩테스트 연습][Java] 약수의 합 / 약수 구하기

📖 문제

자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요.

⛔ 제한 조건

• n은 0 이상 3000 이하인 정수입니다.

💻 입출력 예

n	return
12	28
5	6

 

입출력 예 설명

 입출력 예 #1

12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다.

 

 입출력 예 #2

5의 약수는 1, 5입니다. 이를 모두 더하면 6입니다.

---

 

🔎 약수

: 어떤 수를 나누어 떨어지게 하는 수

 

즉, 정수 $ n $에 대한 약수 $ d $에 대한 조건은 아래 코드처럼 표현할 수 있습니다.

n % d == 0

 

 

약수에 대해 알고 나니,

'그러면 이 조건을 몇 번 실행해야 하는가?' 에 대한 고민을 하게 됩니다.

 

 

가장 단순하게 모든 경우를 실행해 봅니다.

---

 

[방법 1] 가장 단순한 약수 탐색 알고리즘 - 모든 경우를 탐색

• 시간 복잡도 : $ O(n) $

 [탐색 과정]
1. for 문을 1에서 n까지 n번 돕니다.
2. n을 i로 나눈 나머지가 0이면, i는 n의 약수입니다.

class Solution {
    public int solution(int n) {
        int answer = 0;	// answer: 구하고자 하는 정답을 반환할 변수
        
        int sum = 0;	// sum: 약수의 합을 담을 변수
        
        
        for (int i = 1; i <= n; i++) {	// 1부터 n까지 실행
            if ((n % i) == 0) {			// 약수의 조건
                sum += i;				// 약수의 합을 계산
            }
        }
        
        answer = sum;
        return answer;
    }
}

 

 

모든 경우를 탐색하니, 비효율적이라는 생각이 듭니다.

'탐색하는 횟수를 줄일 수 없을까?'

 

 

약수의 특성 중 하나인 약수는 보통 $ n $의 제곱근을 기준으로 한 대칭적인 쌍으로 존재한다는 것을 이용할 수 있을 것 같습니다.

---

 

[방법 2] 효율적인 약수 탐색 알고리즘🌟 - 제곱근까지만 탐색

• 시간 복잡도: $ O(\sqrt{n}) $

 [탐색 과정]

1. for 문을 1에서 n의 제곱근까지 돕니다.

2. n을 i로 나눈 나머지가 0이면, 몫과 i 모두 n의 약수입니다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        int sum = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if ((n % i) == 0) {
                sum += i + (n / i);     // 나눈 값과 몫, 모두 약수입니다.
            }
        }
        
        answer = sum;
        return answer;
    }
}

 

---

위 코드는 약수가 제곱근인 경우 중복으로 더해집니다.

중복 연산을 제거해 줍니다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        int sum = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if ((n % i) == 0) {
                if ((n / i) == i) {
                    sum += i;               // 제곱근의 약수인 경우는 중복되지 않도록 한다.
                } else {
                    sum += i + (n / i);     // 나눈 값과 몫, 모두 약수이다.
                }
            }
        }
        
        answer = sum;
        return answer;
    }
}

 

---

🔎 Java에서 제곱과 제곱근

Math.sqrt(double n)		// n의 제곱근
Math.pow(double a, double n)	// a의 n제곱; a를 n번 곱한 값(= aⁿ)

---

 

 

[방법 3] 단순한 약수 탐색 알고리즘 - $ \frac{n}{2} $개 탐색

• [방법 1]에서 약간 개선
• 시간 복잡도 : $ O(\frac{n}{2}) $

 

 

소수가 아닌 정수 $ n $ 은 보통 약수가 대칭적인 쌍으로 존재합니다.

즉, $ d $가 $ n $의 약수라면 $ \frac{n}{d} $ 도 $ n $의 약수가 됩니다.

이미 알고 있는 $ n $ 을 제외한 약수 중, 가장 큰 수는 $ \frac{n}{k} $입니다. ( $ k $는 $ n $의 약수 중, 가장 작은 소수)

따라서, 1이 아닌 정수 $ n $에 대한 $ \frac{n}{k} $ 중 가장 큰 수는 $ \frac{n}{2} $ 입니다.

 

 

 $ n $까지 모두 탐색하는 [방법 1]에 비해 개선되긴 하였지만, 시간 복잡도면에서 그다지 향상되지 않았음을 알 수 있습니다.