[programmers] 억억단을 외우자

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

starts[] 배열을 s값이 큰 것부터 저장.

이후, calc_all() 함수에서 1부터 e까지 반복문을 돌면서 각 수의 모든 배수에 개수에 +1을 해주어 총 등장 횟수를 구했다.

그리고 priority queue에 s부터 e까지의 등장 횟수를 삽입해, 최종적으로 가장 큰 등장 횟수를 구해 answer의 index 부분에 추가한다.

s가 큰 값부터 반복되기 때문에, 더 작은 s가 나올 경우 포함되지 않은 그 사이 값에 대해서만 priority queue에 추가해주면 된다.

 

---------------------------------------------------풀이----------------------------------------------------

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

// 각 숫자의 인수의 개수 저장
int nums[5'000'001] = {0, };
vector<int> starts;
// 인수가 많은 것 기준 숫자 저장
struct cmp{
    bool operator()(int a, int b){
        if(nums[a] == nums[b]){
            return a > b;
        }
        return nums[a] < nums[b];
    }
};

void calc_all(int e){
    for(int i = 1; i <= e; i++){
        // i의 배수에 개수+1
        for(int j = i; j <= e; j += i){
            nums[j]++;
        }
    }
}

struct idx_cmp{
    bool operator()(pair<int,int> a, pair<int,int> b){
        return a.second < b.second;
    }
};

// s보다 크거나 같고 e보다 작거나 같은 수 중에서 가장 많이 등장한 수는?
// 여러개면 그중 가장 작은 수.
// s의 목록 starts.
vector<int> solution(int e, vector<int> _starts) {
    starts = _starts;
    vector<int> answer(starts.size());
    
    // starts[i]가 큰 값부터 인덱스를 저장
    // index, starts[index]
    priority_queue<pair<int,int>, vector<pair<int,int> >, idx_cmp> idx_answer;
    for(int i = 0; i < starts.size(); i++){
        idx_answer.push(make_pair(i, starts[i]));
    }
    
    // e까지 각각 인수의 개수 저장
    calc_all(e); 
    int min_s = e;
    priority_queue<int, vector<int>, cmp> pq;
    while(!idx_answer.empty()){
        pair<int,int> cur = idx_answer.top();
        idx_answer.pop();
        // 각 s부터 e까지 중에서 제일 많이 등장한 값 찾기
        for(int j = cur.second; j <= min_s; j++){
            pq.push(j);
        }
        answer[cur.first] = pq.top();
        if(cur.second < min_s){
            min_s = cur.second-1;
        }
    }
    return answer;
}

---------------------------------------------------후기----------------------------------------------------

 

에스토스테네스의 체가 떠올라서, 그 방법에 대한 응용으로 각각의 숫자의 배수마다 개수를 1 증가시켜 등장하는 횟수를 구하였다.

그 다음엔 priority queue를 활용하여 s부터 e까지 등장 횟수가 많은 것부터 저장되도록 했는데, 이렇게만 하니까 뒤의 테스트케이스 3개가 시간초과가 났다.

다시 줄일 방법으로 위의 priority queue를 하나로 두고,

start 값이 큰 것부터 계산해 그 인덱스에 매번 top의 값을 추가하는 방식으로 변경하여 통과했다.

즉, s부터 e까지 모든 s에 대해 계속 반복해서 만드는 방식이 문제가 된 것이다.