[Swift] 프로그래머스 코딩테스트 연습> 연습문제> 기사단원의 무기

프로그래머스

 

풀이

기사단원의 번호를 순회하기 위한 포문과 약수를 구하기 위한 포문 두 개의 이중 포문으로 구현하면 number가 최댓값인 100,000일 때 시간복잡도는 백만의 제곱이 되므로 시간초과이다.

메모라이징을 써야할지 고민했는데(아직 감이 없음...) 수학을 응용한 방법이 있었다.

 

number가 10일 때의 약수는 1, 2, 5 10

number가 16일 때의 약수는 1, 2, 4, 8, 16

number가 20일 때의 약수는 1, 2, 5, 10, 20 ......

 

무언가 1부터 number까지 포문이 순회하지 않아도 될 것 같다.

 

16일 때의 약수는 1, 2, 4, 8, 16이면 1, 2는 무언가 곱해져서 약수가 된다. 쌍이 있다는 말이다.

4는 같은 숫자 4가 곱해져 약수가 된 것이다.

 

절반쯤만 구하면 되는데 그 절반이 어디일까????

 

 

1부터 16의 제곱근인 4까지만 순회하면 된다. 

순회하는 변수 i가 16의 약수일 때 약수의 갯수를 더하자.

약수는 쌍이 있으므로 나누어 떨어질 때마다 count + 2를 해주면 되고,

i * i 가 16일 때는 쌍이 없으므로 count + 1 해주자

코드

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