[JS] 자바스크립트 약수 구하기 (Math.sqrt로 시간 복잡도 줄이기)

 

코테 문제를 풀다 보면 인자에 대해 약수를 구해야 하는 경우가 자주 나온다

그때마다 약수 구하는 함수를 새로 짰는데, 계속 반복해서 같은 코드를 관리하다 보니 너무 귀찮아져서 블로그에 기록해두고 필요할 때 마다 복사해서 사용하려고 한다 😊

 

일반적인 코드-1부터 n까지 나머지가 0인 값을 더하기

const findDivisors = (n) => {
    var answer = [1]; //1은 모든 수의 약수니까 약수 배열을 1 포함해 만든다
        for(let i = 2; i <= n; i++){ //1은 했으니까 2부터 고려한다. 2부터 본인까지 차례로 검사한다
            if(n % i === 0) answer.push(i); //나눠진다면(나머지가 없다면, 나머지가 0이라면) 약수배열에 추가한다
        }
    return answer;
}

사람의 사고 방식으로 작성된 코드이다

하지만 1부터 n까지 모든 숫자를 검사하기 때문에 시간 복잡도가 O(n)이라 비효율적이다.

 

더 효율적인 코드- 1부터 √n까지만 검사하기

const findDivisors = (n) => {
    let answer = [0];
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            answer.push(i);
            if (i !== n / i)
                answer.push(n / i);
        }
    }
    return answer;
}

약간 생각만 하면 시간 복잡도를 O(√n)으로 줄일 수 있다.
약수는 대칭성을 가지기 때문에 n의 제곱근까지만 검사하면 된다!

 

예를 들어 16의 경우, 1 로 나눴을때 나머지가 0이니까 약수인데, 이때 몫인 16도 같이 배열에 넣는다

그 다음 2 를 검사하고 통과했을때 2와 8을 배열에 함께 넣는다

그리고 3은 안 되니까 패스하고

마지막으로 루트 16의 값인 4를 검사하면 된다!

 

-> 그러면 16의 약수 1,2,4,8,16을 4번(√n)만에구할 수 있다

 

 

 

이 코드는 프로그래머스 12928 120897 에서 쓰일 수 있다 (계속 추가 예정)

Ⓒ clice lee 

clice의 개발일지 입니다