507. Perfect Number (해석 + 풀이)

Constraints:

• 1 <= num <= 108

의역: 정수 num이 Perfect Number 이면 true 아니면 false 를 반환하라

Perfect Number 란?: 자기 자신을 제외한 약수(진약수)들의 합이 자기 자신이 되는 수를 말한다. 예를 들어, 6의 약수는 자기 자신인 6을 제외한 1, 2, 3이고 진약수들의 합은 1 + 2 + 3 = 6, 즉 자기 자신이므로 6은 완전수이다.

 

예시 1: 28의 약수는 1, 2, 4, 7, 14, 24 여기서 24를 제외한 나머지 숫자들의 합으로 28을 만들 수 있으므로 true 

예시 2: 7의 약수는 1, 7 여기서 7을 제외한 남은 숫자 1만으로는 만드는 것이 불가능 하므로 false

 

풀이:

1. 브루트 포스 (time over)

class Solution {
	// 시간 복잡도 O(n) 공간 복잡도 O(1)
    public boolean checkPerfectNumberTimeOver1(int num) {
        int save = num;
        for(int i=1;i<num;i++){
            if(num%i==0)
                save-=i;
        }
        return save==0;
    }
}

2. 브루트 포스 최적화 (time over)

class Solution {
	// 시간 복잡도 O(n) 공간 복잡도 O(1)
    public boolean checkPerfectNumber(int num) {
        int save = num;
        for(int i=1;i<=num/2;i++){
            if(num%i==0)
                save-=i;
            if(save<0)
                return false;
        }
        return save==0;
    }
}

 3. 브루트 포스 더 최적화 

class Solution {
    // 시간 복잡도 O(루트n) 공간 복잡도 O(1)
    public boolean checkPerfectNumberClear(int num) {
        if(num==1) return false;
        int save = num;
        for(int i=1;i*i<=num;i++) {
            if (num % i == 0) {
                save -= i;
                if (i * i != num&&i!=1)
                    save -= num / i;
            }
        }
        return save==0;
    }
}

4. 유클리드 오일러 정의 이용 

https://en.wikipedia.org/wiki/Perfect_number