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

이 문제는 시작 starts의 변수에서 e파라미터 까지의 범위 숫자의 약수의 개수중 가장 많은 약수를 가진 숫자를 차례로 반환 하는 문제이다.
이때 숫자의 약수의 개수를 starts의 변수 하나마다 재 계산하게 되면 문제를 풀 수 없다.

시작 시점은 랜덤하지만 끝지점은 e 파라미터로 정해져 있기 때문에 1~e까지의 약수 정보를 저장할 리스트를 생성한 후에 약수 정보를 저장하여 해당 범위에서의 약수가 가장 많은 숫자를 찾아야한다.

이때 숫자 1부터 e까지 각 숫자의 시작지점에서 부터 배수의 변수에 +1을 해주게 되면 모든 숫자에 대한 약수의 개수를 알 수 있다.

이렇게 알아낸 정보를 기반으로 단순하게 starts의 숫자 때마다 그 범위를 탐색해서 찾아낼 경우 시간 초과가 뜨게 된다.

나는 해당 숫자와 약수의 개수를 저장할수 있는 자료구조를 만들어 해당 리스트를 약수의 개수로 내림차순 정렬하여 탐색하는 것으로 문제를 해결했다.

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

struct S {
    int i; // 숫자
    int c; // 숫자의 약수 개수
};

S dp[5'000'001];

//약수의 개수를 기준으로 내림차순 정렬
bool cmp(S& a, S& b) {
    if (a.c == b.c)
        return a.i < b.i;
    return a.c > b.c;
}

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer;
	
    //1에 대한 약수와 해당 숫자 정보를 삽입
    for (int i = 1; i <= e; i++) {
        dp[i].i = i;
        dp[i].c++;
    }
	
    //2부터 e까지의 숫자에 대한 약수 정보 삽입
    for (int i = 2; i <= e; i++) {
        for (int k = 1; k <= e / i; k++) {
            dp[i * k].c++;
        }
    }

    sort(dp + 1, dp + e + 1, cmp);
	
    //starts의 변수 ~ e 까지의 숫자중 가장 먼저 나온 숫자를 탐색 
    for (auto s : starts) {
        for (int i = 1; i <= e; i++) {
            if (dp[i].i >= s && dp[i].i <= e) {
                answer.push_back(dp[i].i);
                break;
            }
        }
    }
    
    return answer;
}