[프로그래머스/C++] 억억단을 외우자

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 봤을 때, 최악의 경우 5000000을 1~5000000 사이의 수로 나누어 보면서 개수를 세는 문제인가 생각이 들었다.

하지만 이 경우 N^2이 되기 때문에 불가능 했다.

 

[첫 번째 풀이]

그래서 생각한 아이디어는 결국 곱셈해서 특정한 수가 나온다는 것은 약수의 개수와 같기 때문에 소인수 분해를 이용해 푸는 방법이었다.

 

여기에 e에 대한 수들을 전부 계산할 필요 없이 e/2까지만 계산하면 된다는 생각이 들었다.

(e/2이하의 숫자라면 2를 곱해서 약수의 수가 더 많은 수를 만들 수 있기 때문이다.)

 

그러므로 최악의 경우 2500000*(logN 이하의 소수의 개수)로 문제가 해결 될 것이라고 생각했다.

 

이렇게 문제를 풀고 나니 실제로 답이 맞았다.

 

[다른 풀이]

이 방법 말고도 곱셈을 이용해 약수를 계산하는 풀이가 있었다...

 

내가 나눠서 약수를 구할 생각을 했다면, 반대로 곱해서 어떤 수가 되는지 구하는 방법이 있었던 것이다. 

이 경우 2중 for문을 돌리는데 시간복잡도가

$$e \times (\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4} ... \frac{1}{e})$$

가 된다.

 

여기서 (2/e~1/e)사이에서는 1번 계산하고 (3/e~2/e)사이는 2번 계산한다. (즉, 소수점 부분이 사라진다는 뜻)

그렇기 때문에 nlogn보다 조금 빠른 nlog(log(n))으로 계산이 되기 때문에 더 빠르게 계산이 된다.

(nlog(n)으로 보여서 고민을 했는데, 1.1=1, 1.2=1과 같이 소수점이 커팅이 돼 nlog(log(n))이라 더 빠르다)

 

이후 starts의 숫자가 작아질수록 검사할 수 있는 수의 범위가 늘어나기 때문에 내림차순으로 약수가 가장 많은 수를 계산해 저장했다. 

(3000~e 사이의 수 중에서 약수의 최댓값이 몇인지 알고 있으면, 2999~e사이의 수를 검사한 약수의 최댓값은 3000~e 사이의 수 에서 구한 약수의 최댓값과 2999의 약수의 최댓값을 비교하면 된다.)

 

 

[아이디어 정리]

1. 곱셈을 이용해 약수의 개수를 counting한다.
2. e까지의 수의 약수를 파악했으면, 내림차순으로 e부터 1까지 범위를 늘려가며 최댓값이 어떤 값인지 저장한다.
3. starts에 맞춰 answer를 return한다.

 

Code(소인수 분해)

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer(starts.size());
    vector<int> primeNum(1,2);
    vector<vector<int>> retAns(2,vector<int>(e+1,0));
    for (int i=3; i<=sqrt(e)+2; i++) //e 이하에서 배수가 될 수 있는 소수 구하기
    {
        bool flag=true;
        for (int k=0; k<primeNum.size(); k++)
        {
            if (i%primeNum[k]==0)
            {
                flag=false;
                break;
            }
        }
        if (flag)
        {
            primeNum.push_back(i);
        }
    }

    for (int i=e; i>=e/2; i--) //  만약 e/2보다 작은 수라면 2를 곱한 값이 억억단에 더 많이 나오기 때문....
    {
        int nowNum=i;
        int wrCnt=1;
        for (int j=0; j<primeNum.size(); j++)
        {
            int cnt=1;
            if (primeNum[j]>nowNum)
            {
                break;
            }
            while (nowNum%primeNum[j]==0)
            {
                cnt+=1;
                nowNum/=primeNum[j];
            }
            wrCnt*=cnt;
        }
        if (i<e)
        {
            if (retAns[1][i+1]>wrCnt)
            {
                retAns[1][i]=retAns[1][i+1];
                retAns[0][i]=retAns[0][i+1];
            }
            else
            {
                retAns[1][i]=wrCnt;
                retAns[0][i]=i;
            }
        }
        else
        {
            retAns[1][i]=wrCnt;
            retAns[0][i]=i;
        }
    }
    for (int i=0; i<starts.size(); i++)
    {
        if (starts[i]<e/2)
        {
            answer[i]=retAns[0][e/2];
        }
        else
        {
            answer[i]=retAns[0][starts[i]];
        }
    }
    return answer;
}

 

 

Code(약수의 곱셈)

 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer(starts.size());
    vector<int> retAns(e+1,0);
    for (int i=1; i<=e; i++)
    {
        for (int j = 1; j <= e / i; j++) {
            retAns[i * j]++;
        }
    }
    int maxCnt=0, maxNum=0;
    vector<int> retAns2(e+1,0);
    for (int i=e; i>=e/2; i--)
    {
        if (maxCnt<=retAns[i])
        {
            maxCnt=retAns[i];
            maxNum=i;
        }
        retAns2[i]=maxNum;
    }
    for (int i=0; i<starts.size(); i++)
    {
        if (starts[i]<e/2)
            answer[i]=retAns2[e/2];
        else
            answer[i]=retAns2[starts[i]];            
    }
    return answer;
}

 

 

---

 

시간이 빡빡해서 고민을 많이 했던 문제

프로그래머스