코딩 테스트 - 억억단을 외우자

억억단을 외우자

문제 링크 : 억억단을 외우자

문제 설명

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.

억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.
수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ e ≤ 5,000,000
• 1 ≤ starts의 길이 ≤ min {e,100,000}
• 1 ≤ starts의 원소 ≤ e
• starts에는 중복되는 원소가 존재하지 않습니다.

입출력 예

e	starts	result
8	[1,3,7]	[6,6,8]

풀이 방법

• 억억단에서 가장 많이 등장하려면 (a*b) 형태를 가지고 있어야 하기 때문에 약수가 가장 많은 수가 억억단에서 가장 많이 등장한다는 것을 알 수 있다. 이 때, e의 최대 값은 5,000,000으로 굉장히 큰 수이기 때문에 O(N^2) 이상의 알고리즘으로 할 시에 시간초과가 발생할 확률이 높다.
• 각각의 수를 직접 약수를 구하게 되면 O(N^2)의 시간복잡도를 가지게 되기 때문에, 1단, 2단 순서대로 e단까지의 배수를 직접 구해서 O(NlogN)의 시간복잡도로 e까지의 약수의 개수를 구하고자 했다.
• 다음으로는 e부터 역으로 dp를 통해서 가장 많이 약수를 가지고 있는 수를 저장해가면서, 최소한의 실행만 되게끔 구현했다.
  -> 해당 문제의 핵심은 약수를 직접 구하지 않고, 배수를 통해서 약수의 개수를 구하는 것이 포인트였던 것 같다. 총 문제 풀이의 시간복잡도는 O(NlogN)이 걸리고, N의 최대 값은 5,000,000이기 때문에 아슬아슬하게 통과할 것으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer;
    
    // e까지 약수의 개수 전부 구하기
    vector<int> divisor(e + 1, 0);
    
    for(int i = 1; i <= e; i++){
        for(int j = i; j <= e; j += i){
            divisor[j]++;
        }
    }
    
    // e부터 역으로 dp를 통해서 가장 많이 등장한 수 저장
    vector<int> dp(e + 1, 0);
    dp[e] = e;
    int temp = e;
    
    for(int start : starts){
        if (temp > start){
            for(int i = temp - 1; i >= start; --i){
                if(divisor[dp[i + 1]] > divisor[i]){
                    dp[i] = dp[i + 1];
                }else{
                    dp[i] = i;
                }
            }
            temp = start;
        }
        
        answer.push_back(dp[start]);
    }
    
    return answer;
}