[프로그래머스 | Javascript] 코딩테스트 입문 - 순서쌍의 개수

박기영·2022년 10월 25일
2

프로그래머스

목록 보기
66/159
post-custom-banner

solution 1

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

약수를 구하는 방법이 비효율적으로 보인다.
입력값이 커지면 그만큼 반복 횟수가 기하급수적으로 늘어나기 때문이다.
실제로 4.77ms가 걸리는 테스트 케이스가 있었다.

약수를 구하는 방법을 효율적으로 바꿀 필요가 있다.

solution 2

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를 리턴한다.

위에서 필자가 사용했던 예시를 그대로 적용하면 문제없이 돌아가는 것을 확인할 수 있다.

이 방법은 필자의 풀이와 비교도 안될정도로 빠르다.

profile
나를 믿는 사람들을, 실망시키지 않도록
post-custom-banner

1개의 댓글

comment-user-thumbnail
2023년 8월 23일

안녕하세요
혹시 solution 2 에서는 i 가 조건식으로 인해서 n / 2 까지만 출력이되서 n이 빠지고 answer로 push되는거라
따로 factors.push(n) 를 추가해서 자기자신(n)값을 넣어주고, return factors.length 해야되는거 아닌가요?
자동으로 n 값이 배열길이에 +1를 했다고 출력된다는게 이해가 어려워서요 ㅠㅠ

답글 달기