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

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

프로그래머스

function solution(number, limit, power) {
    // number 의 약수 개수 구하기
    const getNumbers = (number)=>{
        let count = 0
        for (let i = 1; i <= number; i++){
            if(number % i === 0) count ++;
        }       
        return count
    }
    
    let arr = []
    let knight = Array(number).fill(1).map((v, i)=> v*(i+1))
    
    for(let num of knight){
        let number = getNumbers(num)
        
        if(number <= limit){
            arr.push(number)
        }else{
            arr.push(power)
        }
    }
    return arr.reduce((acc, cur)=> acc + cur, 0)
    
}

 

테케 통과는 되지만 문제 제출하면 시간 복잡도에서 문제가 있는듯 했다.

 

약수 개수를 구하는 지점에서 시간 복잡도를 줄여야하는데 

반복문 i = number / 2 까지 하니 틀린 답이 나왔고, 노트에 써보니 절반까지 카운트하는건 약수구하는것과 관계가 없는거였다.

 

결국 지피티에게 시간 복잡도를 낮추는 방법을 물어봤다.

 

방법은 제곱수를 사용하는거였다

i	1	2	3	4	5	6	7	8
j	8	4		2				1

어떤 수 n 을 i 로 나눌 수 있다면, n / i = j 

이때 j 도 반드시 n 의 약수이다

i * ( n / i ) = n 

i 가 √n 을 넘으면 n / i 는 √n 보다 작다.

따라서 √n 까지만 반복문을 돌리면서 확인하고, count 는 2씩 증가시키면 된다

(이때 i * i === n 인 경우에는 count += 1) ex. 6* 6 = 36 -> 약수는 6 한개

function solution(number, limit, power) {
    // number 의 약수 개수 구하기
    const getNumbers = (number)=>{
        let count = 0
        for (let i = 1; i * i <= number; i++){
            if(number % i === 0) {
                count += (i * i === number) ? 1 : 2
            }
        }       
        return count
    }
    let total = 0;
    for (let i = 1; i <= number; i++){
        let count = getNumbers(i)
        total += count > limit ? power : count
    }
    return total
}

 

불필요한 knignt 배열도 없애고 바로 number를 이용하면 된다. 바부.