Lesson 11. Sieve of Eratosthenes - CountNonDivisible #2 (속도 개선)

1. 속도 개선 아이디어

• 배열A의 요소가 가질 수 있는 약수의 개수(혹은 약수가 아닌 수의 개수)는 A.size()를 초과할 수 없다.
• 여기서 약수가 아닌 값을 찾지 말고, 약수인 수를 찾아서 제외한다. 왜냐하면 이전에 사용했던 약수 찾기 알고리즘을 사용하면, N의 약수는 \( O(\sqrt{N}) \) 속도로 찾을 수 있기 때문이다.

 

2. 코드 (C++)

찾은 약수의 개수를 빠르게 제거하기 위해, 배열A의 요소를 map<A[i], 개수>로 정리해 둔다.

#include <map>
#include <cmath>

//약수 찾기
vector<int> get_divisors(int n)
{
    vector<int> divisors = {};

    int i = 1;
    while(i < sqrt(n))
    {
        if(n % i == 0)
        {
            divisors.emplace_back(i);
            divisors.emplace_back(n / i);
        }
        i++;
    }

    if(i * i == n) divisors.emplace_back(i);

    return divisors;
}

vector<int> solution(vector<int> &A) {

    vector<int> result = {}; 
    map<int, int> cache = {}; //배열A 요소 정리
    map<int, int> memo = {}; //이전에 계산된 결과 저장

    //배열A map<A[i], 개수>로 정리
    for(size_t i = 0; i < A.size(); i++)
    {
        auto it = cache.find(A[i]);
        if(it == cache.end())
            cache.insert(pair<int, int>(A[i], 1));
        else
            it->second += 1;
    }

    for(size_t i = 0; i < A.size(); i++)
    {
        auto it = memo.find(A[i]);
        if(it != memo.end()) //이전에 계산된 결과가 있으면 재활용
        {
            result.emplace_back(it->second);
        }
        else
        {
            vector<int> divisors = get_divisors(A[i]); //A[i] 약수 찾기
            int cnt = A.size(); // 결과로 나올 수 있는 최대값으로 설정

            //찾은 약수들의 개수 빼기
            for(const auto v : divisors)
            {
                auto it = cache.find(v);
                if(it != cache.end()) cnt -= it->second;
            }

            //계산된 결과 기록
            memo.insert(pair<int, int>(A[i], cnt));
            result.emplace_back(cnt);
        }
    }

    return result;
}

 

 

3. 결과