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

[문제]

[오답코드]

function solution(number, limit, power) {
    var answer = 0;
    
    for(let i = 1; i <= number; i++)
        {
            let axisnum = 1;
            for(let j = 1; j <= i /2; j++)
                {
                    if(i % j == 0)axisnum++;
                }
            
            if(axisnum > limit)
                {
                    answer += power;
                }
            else
                {
                    answer += axisnum;
                }
        }
    
    return answer;
}

처음 실행했던 코드이다. 이때는 문제가 없다고 생각해 바로 풀었으나, number의 갯수가 최대 10만개까지 되어서 for문을 n으로 두번 돌리면 시간 복잡도가 O(N * N)이 되어서 매우 높게 되어 시간초과가 되었다.

[풀이코드]

function solution(number, limit, power) {
    var answer = 0;
    
    for(let i = 1; i <= number; i++)
        {
            let axisnum = 0;
            for(let j = 1; j <= Math.sqrt(i); j++)
                {
                    if(i % j == 0)
                        {
                            if (i / j == j) axisnum++;
                            else axisnum += 2;
                        }
                }
            
            if(axisnum > limit)
                {
                    answer += power;
                }
            else
                {
                    answer += axisnum;
                }
        }
    
    return answer;
}

[해설]

그래서 문제를 풀기위해 사용한 것이 약수의 제곱근을 이용하는 것이다. Math.sqrt(num)은 숫자의 제곱근 즉 루트를 씌워준다. 4를 넣으면 4의 제곱근인 2가 나오는 것을 알 수있다. 이것을 이용하여 약수를 쉽게 구할 수 있는데 4의 경우 예를들면 약수가 1,2, 4 가 있다. 여기서 1,4 가 서로 곱해진다는 것을 이용하여 문제를 푼다. 4의 제곱근은 2이므로 for문으로 돌아가게 되면 1,2 만돌아간다. 둘다 i인 4에 나눠지기 때문에 2가 올라가야하지만 하나더 사용하여 제곱근일 경우를 제외하면 이미 1, 4는 서로 겹치기 때문에 num += 2를 해준다. 이렇게하면 시간 복잡도를 많이 줄일 수 있다.