[JAVA] 순서쌍의 개수(약수의 개수 구하는 알고리즘)

문제를 읽어보니 약수의 개수를 구하는 것이어서, 약수의 개수 알고리즘을 검색했다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=1; i<=Math.sqrt(n); i++) {
            if(n%i== 0) { 
                // if divisors are equal, count +1
                if(n/i == i) answer ++;
                // otherwise count both
                else answer += 2;
            }
        }
        return answer;
    }
}

Math.sqrt( )는 제곱근 구해주는 거라서 sqrt 말고 i * i <= n 이렇게 해도 무방

그냥 i <= n 으로 해서 n%i == 0 일때 answer ++ 하는 것으로 하면 시간이 너무 오래걸려서 제곱근으로..!

이 부분을

if(n%i== 0) { 
    // if divisors are equal, count +1
    if(n/i == i) answer ++;
    // otherwise count both
    else answer += 2;
}

이렇게 바꿀 수도 있다.

if(n%i== 0) { 
    // if divisors are equal, count +1
    answer ++;
    // otherwise count both
    if(n/i != i) answer ++;
}

2. 다른 풀이 방법

class Solution {
    public int solution(int n) {
        int answer = n>1? 2: 1;
        for(int i = 2; i <= n/2; i++){
            if(n%i == 0) answer++;
        }
        return answer;
    }
}

answer 안에 3항 연산자를 쓸 생각을 하다니.... 신기하다.. 근데 시간은 2번이 더 오래걸리긴 한다..

약수 개수 구하는 알고리즘 생각해놔야겠다.