문제 개요
정수 배열 nums가 주어졌을 때, 배열 안에서 정확히 4개의 약수를 가진 정수들을 찾아 그 약수들의 합을 구하는 문제입니다. 만약 조건을 만족하는 정수가 하나도 없다면 0을 반환해야 합니다.
예를 들어 입력이 [21, 4, 7]이라면 출력은 32입니다.
- 21의 약수는 1, 3, 7, 21로 총 4개 → 약수의 합 = 32
- 4의 약수는 1, 2, 4로 총 3개 → 제외
- 7의 약수는 1, 7로 총 2개 → 제외
따라서 조건을 만족하는 유일한 숫자인 21의 약수 합인 32가 정답이 됩니다.
접근 방법
핵심 아이디어는 각 숫자에 대해 약수의 개수와 약수의 합을 동시에 계산하는 것입니다. 약수는 항상 쌍으로 존재하기 때문에(x = i × (x/i)), i² ≤ x까지만 확인하면 되며, 이를 통해 시간 복잡도를 O(√x)로 줄일 수 있습니다.
풀이 절차는 다음과 같습니다.
- ok()라는 메서드를 정의합니다. 입력값은 x입니다.
- ret := 1 + x, cnt := 2로 초기화합니다. (1과 자기 자신은 항상 약수이므로)
- i := 2부터 i² ≤ x까지 반복하며:
- x가 i로 나누어 떨어지면 ret에 i를 더하고 cnt를 1 증가시킵니다.
- i ≠ x/i라면(즉, i가 제곱근이 아닌 경우) cnt를 1 증가시키고 ret에 x/i를 더합니다.
- cnt가 4이면 ret을 반환하고, 그렇지 않으면 0을 반환합니다.
- 메인 메서드에서는 ret := 0, n := nums의 크기로 초기화한 뒤,
- i를 0부터 n − 1까지 반복하면서 ret에 ok(nums[i])를 누적합니다.
- 최종적으로 ret을 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int ok(int x){
int ret = 1 + x;;
int cnt = 2;
for(int i = 2; i * i <= x; i++){
if(x % i == 0){
ret += (i);
cnt++;
if(i != x / i){
cnt++;
ret += (x / i);
}
}
}
return cnt == 4 ? ret : 0;
}
int sumFourDivisors(vector<int>& nums) {
int ret = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
ret += ok(nums[i]);
}
return ret;
}
};
main(){
vector<int> v = {21,4,7};
Solution ob;
cout << (ob.sumFourDivisors(v));
}입력
[21,4,7]
출력
32
참고: 정확히 4개의 약수를 가진 수의 성질
수학적으로 정확히 4개의 약수를 가진 자연수는 두 가지 형태뿐입니다.
- p × q (서로 다른 두 소수의 곱): 약수는 1, p, q, pq이며, 약수의 합은 (p+1)(q+1)입니다. 예: 21 = 3 × 7
- p³ (소수의 세제곱): 약수는 1, p, p², p³이며, 약수의 합은 1 + p + p² + p³입니다. 예: 8 = 2³
이 성질을 활용하면 소수 판별 기반으로 문제를 더 최적화하여 풀 수도 있습니다.