[Programmers/JS] 약수 구하기

1. 1부터 N까지 나머지가 0인 값을 구하기

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

1부터 주어진 수 n까지 하나씩 대입하며 나머지가 0인 값을 검사하면 이 문제를 간단히 풀 수 있습니다.

시간 복잡도는 O(n) 입니다.

입력값이 커지면 커질수록 모든 수를 다 대입해야 하기 때문에(입력값이 1,000,000,000,000이라면 1부터 1,000,000,000,000까지 하나씩 다 나눠야 하기 때문에) 효율적이지 못한 코드입니다.

코딩테스트는 컴파일에 일정 시간이 지나면 실패 처리하므로 똑같은 문제가 나와도 입력값이 커진다면 통과하지 못할 수 있습니다.

따라서, 더 빠른 계산을 위해 다른 접근이 필요합니다.

2. 제곱근을 활용하기

제곱근을 활용하면 O(n)인 시간복잡도를 O(logN)까지 줄일 수 있습니다.

N의 약수는 √n을 기준으로 대칭으로 존재한다
10의 약수는 1, 2, 5, 10. (√10 = 3.162)

12의 약수는 1, 2, 3, 4, 6, 12 (√12 = 3.464)

20의 약수는 1, 2, 4, 5, 10, 20 (√20 = 4.472)

​

√n 을 기준해서 앞에 나오는 약수 a 를 알아내면, N을 a로 나눠 대칭을 이루는 약수 b도 알아낼 수 있습니다.

따라서, 우리가 체크할 수의 범위는 n의 제곱근까지면 충분합니다.

function solution(n) {
    var answer = [];
   
    // Math.sqrt()는 인자의 제곱근을 구해주는 메서드입니다.
    // sqrt는 square root transform의 약자입니다. 
    // 1부터 제곱근 n까지만 검사합니다. 
    for(let i = 1; i<= Math.sqrt(n); i++){
       // n을 1부터 전부 나눠서 나머지가 0인지 검사합니다. 
	   // 나머지가 0이면 약수로 판별하고 answer 배열에 해당 값을 push
        if(n % i == 0){
            answer.push(i);
            
            // 제곱근 기준으로 앞의 약수만 세서 answer에 push했으므로,
		    // 대칭을 이루는 제곱근 뒤의 약수를 계산해 함께 넣어줘야 합니다.
			// 조건문이 i * i != n인 이유는 대칭에 예외가 있기 때문입니다.
			// 16처럼 √n * √n = n인경우 짝을 이루는 약수가 없어서 한 번만 증가시켜줍니다.
			// 16의 약수 1, 4, 16 
            if( i * i != n){
                answer.push(n / i);
            }
        }
    }
    
    // 알고리즘상 제곱근을 기준으로 대칭하는 값을 쌍으로 넣고 있으므로 
    // 입력값이 24일 경우 순서는 1, 24, 2, 12 ...식으로 배열에 들어가게 됩니다.
    // 오름차순 정렬을 위해 sort를 사용했습니다.
    answer.sort(function(a,b){
        return a - b;
    })
    
    return answer;
}