215. 기사단원의 무기

---

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    
    var numberArray : [Int] = []
    var numbers : [Int] = []
    var answer : Int = 0
    
    numberArray = (1...number).map{$0}

    for i in numberArray {
        var count = 0
       for j in 1...Int(sqrt(Double(i))){
           if i % j == 0 {
               if (j * j) == i {
                   count += 1
               } else {
                   count += 2
               }
           }
       }
       numbers.append(count) 
    }
    
    answer = numbers.map{$0 > limit ? power : $0}.reduce(0,+)
    
    return answer
}

---

사실 이건 온전히 내가 적은건 아니다.

초기에 적은건 다음과 같다.

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    
    var numberArray : [Int] = []
    var numbers : [Int] = []
    var answer : Int = 0
    
    numberArray = (1...number).map{$0}

    for i in numberArray {
        numbers.append((1...i).filter{i%$0 == 0}.count)
    }
    
    answer = numbers.map{$0 > limit ? power : $0}.reduce(0,+)
    
    return answer
}

단순히 약수의 개수를 구하면 된다고 생각했기에, 하나하나 직접 구해서 하는 방식으로 하게되었다.

그런데 이건 위에서도 적었지만 하나하나 다 구해서 배열에 담는 구조이기에 숫자가 커지면 커질수록 그만큼 시간이 오래걸린다는 단점이 존재했다.

그냥 문제가 약수의 개수를 구하고 삼항연산자를 통해 약수의 개수가 특정 값보다 큰지를 확인하고 크면 지정한 값으로 리턴하고, 그것을 그냥 더하면 되었기에 너무 쉬운문제인데? 라고 생각하고 넘어갔다.

하지만 오산이었다. 55.6/100 이라는 점수가 나왔다.

성공한것도 시간대가 꽤나 높게나왔다.

어떻게하면 시간을 줄일 수 있을까? 에 대한 생각을 해보다 도저히 안되어 구글링을 해본 결과

다른 방법을 하나 찾게 되었다.

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    
    var numberArray : [Int] = []
    var numbers : [Int] = []
    var answer : Int = 0
    
    numberArray = (1...number).map{$0}

    for i in numberArray {
        
        if i != 1 {
            numbers.append((1...(i/2)).filter{i%$0 == 0}.count + 1)
        } else {
            numbers.append(1)
        }
        
    }
    
    answer = numbers.map{$0 > limit ? power : $0}.reduce(0,+)
    
    return answer
}

이 방식이다. 하지만 이것도 점수는 전과 같았다, 그나마 나의 초기코드보다는 시간이 단축이 되었지만, 아직도 큰 범위의 수에서는 오래걸린다는것을 의미한다.

매커니즘이 거의 비슷하기 때문이다. 그저 절반으로 나누어서 계산을 했다는 차이 밖엔 없었다.

그래서 더 찾아보았다.

제곱근을 사용하여 구하는 방식이 있다고 한다.

제일위의 코드가 바로 그런 예이다.

아직 제대로 이해를 하지못해서, 내 나름대로 다시 분석을 해봐야 하지 않을까 싶다.

제곱근을 통하여 계산하는건 조만간 deepdive 형식으로 하나하나 파헤쳐봐야겠다.