[Algorithm] Programmers :: 억억단을 외우자

https://school.programmers.co.kr/learn/courses/30/lessons/138475

프로그래머스

 

struct Node
{
    int num = 0;
    int count = 0;
};
 
vector<Node> nodes;
 
bool cmp(const Node& a, const Node& b)
{
    if (a.count == b.count) return a.num < b.num;
 
    return a.count > b.count;
}
 
vector<int> solution(int e, vector<int> starts) 
{
    vector<int> answer;
    nodes.resize(e + 1);
 
    for (int i = 1; i <= e; i++) 
    {
        nodes[i].num = i;
        for (int k = 1; k <= e / i; k++) 
        {
            ++nodes[i * k].count;
        }
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    for (int i = 0; i < starts.size(); ++i)
    {
        int s = starts[i];
 
        for (int j = 0; j < e; ++j)
        {
            if (nodes[j].num >= s && nodes[j].num <= e)
            {
                answer.push_back(nodes[j].num);
                break;
            }
        }
    }
 
    return answer;
}

매번 그렇듯 몰랐던 부분 알게되서 다행인 문제.

1 ~ e까지 숫자의 각각 약수의 개수를 구해서 범위내의 숫자 중 약수가 가장 많은 수를 알아야하는 문제이다.

 

특정 숫자의 약수의 개수를 구할 때는 보통 아래와 같이 작성할 것이다. (i가 특정숫자이다.)

  
     
        for (int j = 1; j * j <= i; ++j)
        {
            if (j * j == i)
            {
                nodes[i].count += 1;
            }
            else if (i % j == 0)
            {
                nodes[i].count += 2;
            }
        }
   

살짝 다르게표현하자면, 루트i 까지만 반복문을 수행하면서 나누어 떨어질경우 count+=2를 하고 (나누어 떨어진다는것은 두 숫자 다 약수라는 것),  같은 숫자를 곱했을 때 특정숫자가 된다는것은 말그대로 같은숫자라 count += 1만 해주는 것이다. 

다만 보통 루트함수는 자원을 많이 먹기때문에 j * j <= i 이런식으로 작성한다는 것은 다 알 것이다.

 

그리고 이후의 로직을 위해 각 숫자마다의 약수개수를 구조체화해서 보관한다. 

왜냐하면 약수개수를 기준으로 내림차순 해야하니까... 문제에서는 범위내의 가장 많은 약수의개수를 가진 숫자를 알아내야한다고 적혀있기 때문이다.

 

내림차순하면 무조건 약수개수가 가장 많은거부터 앞에 저장되어있으니까 해당 숫자만 적정범위인지 검사하고 answer에 푸쉬하면 된다.

 

자 근데 약수의 개수를 구할 때 앞서 말했던 방식으로 하면 반드시 시간초과가 나온다.

왜? 사실 대충 생각만해도, e가 최대 500만인데 500만이라는 숫자 하나만 약수개수구하려해도 2300번대정도의 반복문이 수행된다. 근데 숫자는 1 ~ 500만이다.  2000번대의 반복문이 만번만 반복되도 2천만이라서 아마 충분히 안될거란걸 알 수 있다.

 

그러면 어떻게 해야하는가? 애초에 문제에서는 단순히 특정숫자의 약수의개수를 구하는것보다는 더 넓게 1 ~ e까지의 숫자의 약수의개수를 구해야 한다는 것을 알 수 있다.

관련해서는 위 코드랑 같진 않지만, 수학적으로 잘 설명한 글이 있어 링크를 걸어본다.

https://m.blog.naver.com/nwc1718/221723394278

두 수 사이의 모든 자연수의 약수의 개수를 구하는 알고리즘