function solution(n) {
let factors = [];
for(let i = 1; i <= n; i++){
if(n % i === 0){
factors.push(i);
}
}
return factors.length;
}
약수를 구하는 방법이 비효율적으로 보인다.
입력값이 커지면 그만큼 반복 횟수가 기하급수적으로 늘어나기 때문이다.
실제로 4.77ms가 걸리는 테스트 케이스가 있었다.
약수를 구하는 방법을 효율적으로 바꿀 필요가 있다.
function solution(n) {
let factors = [];
for(let i = 1; i <= n / 2; i++){
if(n % i === 0){
factors.push(i);
}
}
return factors.length + 1;
}
예시를 몇 개 찾아서 규칙을 찾아봤더니,
입력값의 절반까지만 반복하고, 거기까지 구한 약수의 개수에서 +1을 해주면 총 약수의 개수가 나왔다.
21 : 1,3,7,21
25 : 1,5,25
36 : 1,2,3,4,6,9,12,18,36
...
당연하게도 절반의 연산만 진행하므로
시간은 줄었다. 그래도 4.21ms까지 걸린다.
function solution(n) {
let ans = 0;
for (let i = 1; i < Math.sqrt(n); i++)
if (n%i === 0) ans+=2;
return Number.isInteger(Math.sqrt(n)) ? ans+1 : ans;
}
아무래도 소인수분해를 이용하신 것 같다.(소인수분해 문제 풀었을 때 코드라고 생각되기 때문)
for문에서 제곱근 처리를 했기 때문에 하나의 약수가 발견될 때마다 +2를 해주신 것 같다.
제곱근이 정수로 딱 떨어지면 +1을, 아니라면 그대로 ans를 리턴한다.
위에서 필자가 사용했던 예시를 그대로 적용하면 문제없이 돌아가는 것을 확인할 수 있다.
이 방법은 필자의 풀이와 비교도 안될정도로 빠르다.
안녕하세요
혹시 solution 2 에서는 i 가 조건식으로 인해서 n / 2 까지만 출력이되서 n이 빠지고 answer로 push되는거라
따로 factors.push(n) 를 추가해서 자기자신(n)값을 넣어주고, return factors.length 해야되는거 아닌가요?
자동으로 n 값이 배열길이에 +1를 했다고 출력된다는게 이해가 어려워서요 ㅠㅠ