[Kotlin] Programmers Lv. 1 약수의 합

https://school.programmers.co.kr/learn/courses/30/lessons/12928

프로그래머스

Code

---

class Solution {
    //fun solution(n: Int): Int = (1 .. n).filter { n % it == 0 }.sum()
    fun solution(n: Int): Int{
        var set = hashSetOf<Int>()
        for (i in 1 .. sqrt(n.toDouble()).toInt()){
            if (n % i == 0) {
                set.add(i)
                set.add(n / i)
            }
        }
        return set.sum()
    }
}

---

이 문제는 약수를 구하는 방법을 알고있는지 묻는 문제다.

 

물론 누가 모를까. n번 순회하면서 다 나눠보면 되는데

fun solution(n: Int): Int = (1 .. n).filter { n % it == 0 }.sum()

이게 그 방법이다. n번 확인하면서 각각 숫자가 n의 약수인지 확인하는 것이다.

그러면 시간 복잡도가 O(n)이 된다. 

대략적으로 이정도 메모리와 시간이 소요된다.

 

근데 이건 너무 비효율적이다.

 

 

그래서 사용하는 방법은 약수의 성질을 이용하는 것이다.

fun solution(n: Int): Int{
    var set = hashSetOf<Int>()
    for (i in 1 .. sqrt(n.toDouble()).toInt()){
        if (n % i == 0) {
            set.add(i)
            set.add(n / i)
        }
    }
    return set.sum()
}

그러면 시간 복잡도가 O(log n)이 된다. 

 

대략적으로 이정도 메모리와 시간이 소요된다.

 

시간상으로 큰 차이가 안나보일수 있다.

이 문제는 최대 3000의 숫자까지밖에 안들어가지만, 그 숫자가 커질수록 더 큰 차이가 나게 된다.