[알고리즘] 약수 구하기 기본 & 제곱근 (Math.sqrt)

알고리즘 출처 : 프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/120808

약수를 구하는 문제이다.

제곱근의 접근을 모르면 for문을 사용하여 문제를 해결한다.

약수 구하기

O(n)의 시간 복잡도를 가진다.

1. 1 에서 n까지 for 문을 돈다.
2. n 을 i로 나눈 나머지가 0이면 i는 n의 약수이다.

function solution(n) {
    const answer = [];
    
    for (let i = 1; i <= n; i++) {
        if (n % i === 0) {
            answer.push(i);
        }
    }
    
    return answer;
}

제곱근의 접근을 이해하면 시간복잡도가 간결해진다.

O(log n)의 시간 복잡도를 가진다.

아래의 공식을 문자 그대로 이해하고 구현하는 것이 중요하다.

1. 제곱근 이하의 숫자중에 n 을 i로 나눈 나머지의 값이 0이면
2. i는 n의 약수이다.
3. n을 i로 나눈 값도 n의 약수이다.

그러므로 아래와 같은 코드를 갖게된다.

1. 중복 제거를 위해 Set를 생성한다.
2. 1에서 제곱근까지 for문을 돈다.
   • n을 i로 나눈 나머지가 0이면 i는 n의 약수이다.
   • 그리고 n을 i로 나눈 값도 n의 약수이다.
3. 위 결과값을 Set에 추가한다.
4. (옵션) 오름차순으로의 정렬이 필요한 경우 정렬한 값을 출력한다.

function solution(n) {
    const numberSet = new Set();
    
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            numberSet.add(n / i);
            numberSet.add(i);
        }
    }
    
    return [...numberSet].sort((a,b) => a-b);
}

문제를 푸는 것도 중요하지만
다양한 접근 패턴을 이해하여 적재적소에 사용하면 더 좋은 결과물을 얻을 수 있다.