약수의 개수를 구하는 알고리즘 수행 시간 비교

 

프로그래머스를 풀다가 누군가 독특한 방법으로 약수의 개수를 구하는 걸 발견해서 성능을 테스트 해보기로 했다.

 

우선 내가 작성한 알고리즘이다.

 

num까지 순회할 필요 없이 제곱근까지 순회하며 2개씩 더하는 방식이다.

 

int getNumberOfDivisor(int num = 1020)
{
    int last = sqrt(num);
    int count = (pow(last, 2) == num) ? -1 : 0;

    for (int i = 1; i <= last; ++i)
        if (num % i == 0)
            count += 2;

    return count;
}

 

아래는 다른 사람의 방법이다.

처음에 이렇게 간단하게 구해지나?라고 생각했다.

 

살펴보니, 약수의 개수 = 자신을 배수로 갖는 수의 개수를 이용한 방법이었다.

1일 경우 1, 2, 3, 4, ..

3일 경우 3, 6, 9, 12, ..

 

굉장히 간단한 방식이다.

 

int getNumberOfDivisor(int num = 1020)
{
    vector<int> divisorCounts(num + 1, 0);

    for (int i = 1; i <= num; ++i)
        for (int j = i; j <= num; j += i)
            ++divisorCounts[j];

    return divisorCounts[num];
}

 

내 방법의 경우 num의 약수의 개수를 구할 때 num까지의 약수의 개수는 계산하지 않아도 되지만, 다른 사람의 방법은 1 ~ num까지를 모두 계산해야 한다.

 

퀵 벤치에서 테스트해 본 결과, num = 1020 하나에 대한 약수의 개수를 구할 때 내 방식이 120,000배 빨랐다.

 

 

위는 num = 1020 하나에 대한 테스트였고 이번에는 1 ~ num까지의 모든 약수의 개수를 계산해 비교해보기로 했다.

 

for문을 추가한 내 방법이다.

 

vector<int> countDivisors(int num = 1020)
{
    vector<int> divisorCounts(num + 1, 0);

    for (int i = 1; i <= num; ++i)
    {
        int last = sqrt(i);
        int count = (pow(last, 2) == i) ? -1 : 0;

        for (int j = 1; j <= last; ++j)
            if (i % j == 0)
                count += 2;
                
        divisorCounts[i] = count;
    }
    
    return divisorCounts;
}

 

더 반복할 필요 없이 divisorCounts[num]을 반환하던 것을 divisorCounts 벡터를 반환하도록 하면 되는 다른 사람의 방법이다.

 

vector<int> countDivisors(int num = 1020)
{
    vector<int> divisorCounts(num + 1, 0);

    for (int i = 1; i <= num; ++i)
        for (int j = i; j <= num; j += i)
            ++divisorCounts[j];

    return divisorCounts;
}

 

차이가 꽤 줄긴 했지만 이번에도 내 방식이 7.4배 빨랐다.

 

코딩 테스트에서 약수의 개수를 구하는 알고리즘이 잘 생각나지 않고 문제의 시간 조건이 까다롭지 않은 경우라면 다른 사람의 간단한 풀이를 이용해도 될 것 같다.