프로그래머스: 기사단원의 무기

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

프로그래머스

 

풀이

처음 풀었던 방식 ->

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var divisors = 0

    for i in 1 ... number {
        var count = 0
        for j in 1 ... i {
            if i % j == 0 {
                count += 1
            }
        }
        if count > limit {
            count = power
        }
        divisors += count
    }


    return divisors
}

시간 초과 발생......

 

단순히 이중 for문을 사용하게 되면 1부터 number까지 하나하나 다 구해야해서 

number의 범위인 100,000개까지 계산 시 속도는 현저히 떨어지므로

number의 제곱근을 이용한다.

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var divisors = 0
    
    for i in 1 ... number {
        var count = 0
        let sqrtNumber = Int(sqrt(Double(i)))
        
        for j in 1 ... sqrtNumber {
            if i % j == 0 {
                if j * j == i {
                    count += 1
                } else {
                    count += 2
                }
            }
        }
        
        if count > limit {
            count = power
        }
        divisors += count
        count = 0
    }
    
    return divisors
}