[프로그래머스] level.1 기사단원의 무기 ❗️(약수)

 

프로그래머스

---

나의 풀이 

 

 

틀린 풀이 1

function solution(number, limit, power) {
    let result = 0
    const box = []
    for(let i = 1; i<=number; i++){
        const divisorCount = getDivisor(i)
        box.push(divisorCount)
    }
    
    return box.reduce((acc,cur) =>{
       if(cur > limit){
           acc += power
       }else{
           acc += cur
       } 
        return acc
    },0)
    
}

function getDivisor(number){
        const divisor = []
        for(let i = 1; i<=number; i++) {
            if((number % i) === 0){
                divisor.push(i)
            }
        }
        return divisor.length
    }

시간 복잡도가 O(n^2) 이라서 일부 케이스가 시간초과가 나온다. 

 

 

 

틀린 풀이 2

function solution(number, limit, power) {
    let result = 0
    for(let i = 1; i<=number; i++){
        const divisorCount = getDivisor(i, limit, power)
        result += divisorCount
    }
    return result
}

function getDivisor(number, limit, power){
        let count = 0
        for(let i = 1; i<=number; i++) {
            if(number % i === 0){
                count += 1
            }
            if(count  > limit ){
                return power
            }  
        }
        return count 
    }

시간 복잡도가 O(number*limit) 이라서 될 것 같았는데 이 역시 일부 케이스가 시간초과된다. 

 

 

정답 코드

 

옛날에 제곱근을 활용해서 시간복잡도를 줄였던 기억이나서  제곱근 활용해서 풀었다.  

 

예를들어 30의 약수는 1,2,3,5,6,10,15,30 이다.  

이는 1 x 30, 2 x 15, 3 x 10, 5 x 6 과 6 x 5, 10 x 3, 15 x 2, 30 x 1 이 된다.

잘보면 앞의 4개와 뒤의 4개는 역순 관계가 성립한다.  따라서 앞에 4개만 찾으면 나머지 4개는 구하기가 쉽다. 

그래서 추가된 코드가 다음과 같다.

if(i !== number/i){
    count+= 1
}

위에 예제처럼 30의 약수를 구할 때

30 % 1 === 0 이다. 따라서 약수 1이 구해지고 

 

30/1 = 30 으로 1의 짝인 30이 구해진다.  

 

여기서 중요한점은 number/i 만 해준게 아니고 i !== number/i를 해줬다는 것이다. 

4의 약수는  1, 2, 4   짝지어보면     1x4, 2x2 와 2x2  4x1 이다. 즉 2가 겹치게된다. 따라서  숫자의 제곱근이 약수가 되는 경우는 제외시켜줘야한다. 

 

 

function solution(number, limit, power) {
    let result = 0
    for(let i = 1; i<=number; i++){
        const divisorCount = getDivisor(i, limit, power)
        result += divisorCount
    }
    return result
}
function getDivisor(number, limit, power){
        let count = 0
        if(number === 1) return 1
        for(let i = 1; i<=Math.sqrt(number); i++) {
            if(number % i === 0){
                count += 1
                if(i !== number/i){
                    count+= 1
                }
            }
            if(count  > limit ){
                return power
            }  
        }
        return count 
    }