완전수 — Leetcode 507

원래 문제 링크:https://leetcode.com/problems/perfect-number/

이 문제에서 우리는 주어진 정수 n이 모든 양의 약수(n 자체는 제외)의 합과 같은 정수로 정의되는 완전수인지 여부를 결정하도록 요청받습니다.

이를 수행하는 가장 직관적인 방법은 2에서 n / 2까지 계속 반복하고 누계를 추적하는 것입니다. 그러나 당연히 이것은 큰 숫자에 대해 시간 제한 초과 예외를 제공합니다.

그래서 더 빠른 해결책을 찾았습니다. 왜냐하면 수학적으로 요인을 찾을 때 합계의 일부가 되어야 하는 요인에 해당하는 또 다른 요인이 항상 있기 때문입니다(예: n = 28이고 2에서 시작하면 28 / 2 = 14도 요인이어야 하며 간격을 더 빨리 좁힐 수 있으므로 이 방법으로 루프 수를 절반으로 줄일 수 있습니다. 이것은 내가 생각해 낸 허용된 솔루션입니다.

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num == 1) {
            return false;
        }
        int sum = 1;
        int left = 2;
        int right = num / 2;
        while (left < right) {
            if (num % left == 0) {
                sum += left;
                sum += (num / left);
                right = num / left;
            }
            left++;
        }
        return sum == num;
    }
}