문제 개요
양의 정수 하나를 유일한 인수로 받아, 해당 숫자를 나누어 떨어지게 하는 모든 수(약수)를 배열로 만들어 반환하는 JavaScript 함수를 작성해야 합니다.
예시 −
입력 값이 다음과 같다면 −
const num = 12;
출력 결과는 다음과 같아야 합니다 −
const output = [1, 2, 3, 4, 6, 12];
접근 방식
이 문제는 반복문을 활용해 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 1은 모든 양의 정수의 공통 약수이므로 결과 배열에 미리 포함시킵니다.
- num/2보다 큰 수 중 num 자신을 제외한 어떤 수도 약수가 될 수 없으므로, 탐색 범위를 num/2까지만 제한하면 불필요한 연산을 줄일 수 있습니다.
- 짝수는 2부터 1씩 증가시키며 검사하고, 홀수는 짝수를 약수로 가질 수 없으므로 3부터 2씩 건너뛰며 홀수만 검사해 성능을 최적화합니다.
예제 코드
다음은 전체 코드입니다 −
const findFactors = (num = 1) => {
let half = Math.floor(num / 2);
const res = [1]; // 모든 해에는 1이 포함됩니다.
let i, j;
num % 2 === 0 ? (i = 2, j = 1) : (i = 3, j = 2);
for (i; i <= half; i += j) {
if(num % i === 0){
res.push(i);
};
};
res.push(num);
return res;
};
console.log(findFactors(12));
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다 −
[ 1, 2, 3, 4, 6, 12 ]
코드 단계별 설명
- 탐색 범위 설정: Math.floor(num / 2)로 half 값을 계산해, num 자신을 제외한 가장 큰 후보 약수까지만 반복문을 실행합니다.
- 짝수·홀수 분기 처리: 삼항 연산자를 이용해 num이 짝수면 시작값 2와 증분 1(i=2, j=1)을, 홀수면 시작값 3과 증분 2(i=3, j=2)를 설정합니다. 홀수는 짝수인 약수를 가질 수 없기 때문입니다.
- 약수 판별: 반복문 안에서 num % i === 0 조건으로 i가 num을 나누어 떨어지게 하는지 확인하고, 참이면 결과 배열 res에 추가합니다.
- 마무리: 자기 자신(num)은 항상 약수이므로 마지막에 push한 뒤 완성된 배열을 반환합니다.
이 알고리즘의 시간 복잡도는 O(n/2), 즉 O(n)입니다. 더 빠른 처리가 필요하다면 √n까지의 약수만 확인한 후 그 짝(pair)을 함께 추가하는 방식으로 시간 복잡도를 O(√n)까지 개선할 수 있습니다.