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 이라는 점수가 나왔다.

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

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

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

위의 코드가 바로 그런 예이다. 아직 제대로 이해를 하지못해서, 내 나름대로 다시 분석을 해봐야 하지 않을까 싶다.

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