[ALGORITHM] LEVEL3 - 억억단을 외우자

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

프로그래머스

과정

1. starts가 정렬이 되어 있지 않으므로 starts의 값과 해당 index를 vector에 담아준 뒤 starts의 값이 작은 순으로 정렬해준다.
2. e이하의 숫자들에 대한 등장 횟수를 구한다.
3. 등장 횟수의 내림차 순 숫자에 대한 오름차 순으로 정렬을 한다.
4. start_arr(starts의 값과 인덱스가 담겨 정렬이 된 배열)에서 앞부터 값을 꺼내 만약 starts의 값보다 작다면 answer에 해당 인덱스에 cnt 초기 숫자 값을 저장해준다.

start_arr = <start값, 초기 인덱스> (정렬을 이용하여 연산을 줄이기 위함)

cnt = <초기 숫자, 등장 횟수> (정렬을 이용하여 반복적인 탐색을 피하기 위함)

생각해보기

값들의 count 횟수를 구할 때 메모이제이션과 소수만을 이용하여 계산하면 훨씬 빠르지 않을까...?

코드

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

//정렬 후 스택에 넣었던 걸 뺀다? -> 숫자순 이므로 가능 할 수도 sqrt
vector<pair<int, int> > cnt;
vector<pair<int, int> > start_arr;

bool cmp(const pair<int, int>& a, const pair<int, int>& b ){
    if(a.second == b.second){
        return a.first < b.first;
    }
    return a.second > b.second; 
}

void calc(int e){
    for(int i=0;i<=e;++i){
        cnt[i].first=i;
        cnt[i].second=0;
    }
    
    for(int i=1;i<=sqrt(e);++i){
        for(int j=i;j*i<=e;++j){
            cnt[i*j].first=i*j;
            if(i==j)
                cnt[i*j].second+=1;
            else
                cnt[i*j].second+=2;
        }
    }
}

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer(starts.size());
    cnt.resize(e+1);//곱한 값이 최대 e까지 밖에 안나오므로
    
    int len=starts.size();
    for(int i=0;i<len;++i){
        start_arr.push_back({starts[i],i});
    }
    sort(start_arr.begin(),start_arr.end());
    calc(e);
    sort(cnt.begin(),cnt.end(),cmp);
    
    int idx=0;
    for(int i=0;i<len;++i){
        while(cnt[idx].first < start_arr[i].first)
            ++idx;
        answer[start_arr[i].second] = cnt[idx].first;

    }
    
    
    return answer;
}