[프로그래머스 Level 3] 억억단을 외우자 (C++)

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

프로그래머스

 

 

생각 흐름

1. 소인수 분해로 약수의 개수 구해보기.
2. 시간 복잡도 확인 후 포기.
3. 두 수의 곱셈의 결과가 결국 약수임을 깨달음.
4. 2중 for문으로 약수의 개수 저장
5. e 값부터 1의 방향으로 약수의 개수가 가장 많은 값을 갱신하며 약수의 개수가 가장 많은 수를 저장

 

#include <vector>

using namespace std;

int c[5000001];
int maxC[5000001];

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer;
    
    for(int i = 2; i<=e; i++){
        for(int j =1; j<=e; j++){
            if(i*j>e)
                break;
            c[i*j]++;
        }
    }
    
    int maxNum, maxCount = 0;
    for(int i=e; i>=1; i--){
        if(maxCount<=c[i]){
            maxNum=i;
            maxCount=c[i];
        }
        maxC[i]=maxNum;
    }
    
    
    
    for(int i = 0 ; i<starts.size(); i++){
        answer.push_back(maxC[starts[i]]);
    }
    
    
    return answer;
}