[Swift] countFactors 약수구하기 코딜리티 코딩테스트

특정 수의 약수를 구하는 방법은 가장 쉬운 방법으로

1~ 반값 만큼 반복문을 돌린후

0으로 나누어 떨어지는값을 고르면 된다.

public func solution(_ N : Int) -> Int {
    if(N == 1 ){return 1}
    
    var arr = [N]

    let center = N/2
    for i in 1...center{
        if(N%i == 0){
            arr.append(i)
        }
    }
    return arr.count
}

이 과정은 0(N)의 복잡도를 가지게된다. ( O(N/2) 이긴 하지만..)

이보다 빠른 방법은 O(sqrt(N))이 있다.

예를 들어 24 의 약수를 구해보자

1,2,3,4,6,8,12,24 이렇게 약수가 있다.

여기서 약수를 구할때는

0으로 나누어 떨어지는지에대한 조건으로 구하는건 같으나

반복의 횟수가 달라진다

while i * i <= N {
	//로직
	i += 1
}

이렇게 반복수가 제곱만큼 줄어들수있다.

이유는 다음과같다

예로 24가 3으로 나누어 떨어진다면 그 값도 약수이므로

두가지 약수가 나온다는것이다.

24/3 = 8

3뿐만 아니라 8 또한 24의 약수다

다른 예로 2 나 4도 마찬가지다

24/2 = 12
24/4 = 6

2,4와 6,12 모두 24의 약수이다.

24의 제곱근은 4.xxx 이다.

그러므로 5 이상 부터는 셀 필요가없다.

이미 6, 8,12,24 가 구해졌기 때문이다.

여기서 단 한가지 예외가 있다.

예로 25의 약수를 구해보자

25의 제곱근인 1~ 5까지만 반복을 돌릴것이고

2,3,4는 25와 0으로 나누어 떨어지지 않으므로 제외한다

5는 나누어 떨어진다.

그런데 5와 25/5는 같은 값이다.

5
25 /5 =5

이렇게 두케이스는 같으므로 이렇게 딱 나누어 떨어지는경우는

1개의 약수만 구해진다.

public func solution(_ N : Int) -> Int {

    var i = 1
    var answer = 0
    while i*i <= N {
        if(N % i == 0){
            if(i*i == N){
                answer += 1
            }else{
                answer += 2
            }
        }

        i += 1 
    } 
    return answer
}