[LV1] 기사단원의 무기

프로그래머스 LV1 > 연습문제 > 기사단원의 무기

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

[문제해결]
1. 약수는 n으로 나눈 나머지가 0인것으로 판단한다.
2. 약수의 갯수는 약수들을 배열에 넣고 배열의 길이로 계산했다.
3. 리밋에 걸리면 power을 더해주고, 안걸리면 그대로 더해준다.
** 타임아웃에 주의하며 약수구하는 시간을 어떻게든 줄여본다.

일단 의식의 흐름대로 작성했고.

function solution(number, limit, power) {
    const divisors = []; // 약수의 갯수 순서
    
    for(let i=1; i <= number; i++){
        let temp = [];
        for(let j=1; j<=i; j++){
            if(i % j === 0) temp.push(j);
        }
        divisors.push(temp.length)
    }
    
    const answer = divisors.reduce((acc, res)=>{
        res > limit ? acc+=power : acc+=res
        return acc
    })
    
    return answer
  
    // return answer;
}

 

이중포문 도는데 왠지 타임아웃 날것같았는데 역시나 시간초과..
약수 구하는공식에 /2를 해줘서 반으로 줄여보자

 

function solution(number, limit, power) {
    const divisors = []; // 약수의 갯수 순서
    
    const getDivisors = (num) => { // 약수구하는 공식을 수정했다
        const tempDivisors = [];
        for(let i = 1 ; i <= num/2 ; i++){
            if(num % i === 0) tempDivisors.push(i);
        }
        return [...tempDivisors, num];
    }
    
    for(let i=1; i<=number; i++){ //약수의 갯수만큼 푸시
        divisors.push(getDivisors(i).length);
    }
    
    const answer = divisors.reduce((acc, res)=>{
        res > limit ? acc+=power : acc+=res
        return acc
    })
    
    return answer
  
    // return answer;
}

 

통과는 했지만 역시나 시간이 꽤 걸리는것같다.  약수구하는 문제가 꽤 많이 등장하는데, 모든 배열을 판단하는것보다 sqrt를 쓴다든지, 나누기 2를 한다든지, 하는 방법을 익혀두면 도움이 될것같긴 하다.