1390. 네 개의 약수

Source: Dev.to

문제 설명

정수 배열 nums가 주어지면, 해당 배열에 있는 정수 중 정확히 네 개의 약수를 가진 정수들의 약수 합을 반환합니다. 그런 정수가 배열에 하나도 없으면 0을 반환합니다.

예시

예시 1

입력: nums = [21,4,7]
출력: 32

설명:

• 21은 4개의 약수를 가집니다: 1, 3, 7, 21
• 4는 3개의 약수를 가집니다: 1, 2, 4
• 7은 2개의 약수를 가집니다: 1, 7

오직 21만 조건에 부합하며, 그 약수들의 합은 1 + 3 + 7 + 21 = 32 입니다.

예시 2

입력: nums = [21,21]
출력: 64

두 요소가 모두 21이므로 각각 32씩 더해 총합은 64가 됩니다.

예시 3

입력: nums = [1,2,3,4,5]
출력: 0

배열에 정확히 네 개의 약수를 가진 수가 없습니다.

제약 조건

1  4) {
                // 네 개보다 많은 약수 – 조건 불충족.
                return 0;
            }
        }
    }

    return ($cnt === 4) ? $sum : 0;
}

// 테스트 케이스
echo sumFourDivisors([21,4,7]) . "\n";          // Output: 32
echo sumFourDivisors([21,21]) . "\n";           // Output: 64
echo sumFourDivisors([1,2,3,4,5]) . "\n";       // Output: 0
?>

풀이 (PHP)

<?php
function sumFourDivisors(array $nums): int {
    $total = 0;
    foreach ($nums as $num) {
        $total += fourDivisorsSum($num);
    }
    return $total;
}

function fourDivisorsSum(int $n): int {
    $cnt = 0;
    $sum = 0;
    for ($i = 1; $i * $i <= $n; $i++) {
        if ($n % $i === 0) {
            $cnt++;
            $sum += $i;
            $other = intdiv($n, $i);
            if ($other !== $i) {
                $cnt++;
                $sum += $other;
            }
            if ($cnt > 4) {
                // 네 개보다 많은 약수 – 조건 불충족.
                return 0;
            }
        }
    }

    return ($cnt === 4) ? $sum : 0;
}

// 테스트 케이스
echo sumFourDivisors([21,4,7]) . "\n";          // Output: 32
echo sumFourDivisors([21,21]) . "\n";           // Output: 64
echo sumFourDivisors([1,2,3,4,5]) . "\n";       // Output: 0
?>

주요 알고리즘

1. 반복: 입력 배열의 각 원소를 순회합니다.
2. 판별: 현재 숫자를 제곱근까지 탐색하면서 약수를 세고 합산하여 정확히 네 개의 약수를 가지는지 확인합니다.
3. 누적: 조건을 만족하는 숫자의 약수 합을 전체 합에 더합니다.

복잡도 분석

• 시간 복잡도: O(n × √m), 여기서 n은 nums 길이, m은 nums 안의 최대값입니다.
• 공간 복잡도: 입력 배열을 제외하고 O(1)의 보조 공간을 사용합니다.