[Programmers] 기사단원의 무기 - Javascript

INDEX

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

프로그래머스

 

Solution

약수를 구하는 알고리즘을 구현하는게 핵심입니다.

예를 들어 number 가 4인 경우 1, 2, 3, 4의 각 약수를 구해 Array 에 담는다면 단순하겠지만 시간초과에 걸릴겁니다.

 

number의 약수라는건 그 약수들의 곱으로 number 를 만들 수 있다는 의미이므로 1부터 시작해서 만들 수 있는 배수의 개수를 세주었습니다.

 

number 가 4인 경우,  [0, 0, 0, 0] 과 같은 0으로 이루어진 배열을 만든 다음, 1부터 시작해 number보다 커지기 전까지 구구단처럼 곱셈을 해주어 카운트 배열을 만들어줍니다.

Example) number = 4

1 X 1 = 1, 1 X 2 = 2, 1 X 3 = 3, 1 X 4 = 4  =>  [1, 1, 1, 1]

2 X 1 = 2, 2 X 2 = 4 => [1, 2, 1, 2]

3 X 1 = 3 => [1, 2, 2, 2] 

4 X 1 = 4 => [1, 2, 2, 3]

 

이렇게 약수의 개수를 담은 배열을 만들었고 limit 을 넘은 기사단원은 power 값으로 대체해 합을 구하면 됩니다.

function solution(number, limit, power) {
    let answer = new Array(number).fill(0);
    for(let i=1; i<=number; i++){
        let multiplier = 1;
        while(i*multiplier <= number){
            answer[i*multiplier - 1] += 1;
            multiplier+=1;
        }
    }
    let sum = 0;
    for(let item of answer){
        if(item > limit) sum += power;
        else sum+= item;
    }
    return sum;
}