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

이 문제는 구현 문제이다. 

 

문제 제목 보고 1억 * 1억 배열이라 다른 방법을 사용할 줄 알았는데 입력으로 주어지는 e가 최대 5백만이라 배열로 만들 수 있었다.

 

가장 처음 나오는 이중 for문에 5,000,000을 넣고 카운트해보면 약 7,800만 정도의 연산을 수행하게 된다. 따라서 1초 안에 cnt를 모두 셀 수 있다.

 

범위를 세는 부분이 언뜻 시간을 초과할 것처럼 보이지만, starts 배열을 내림차순 정렬한 뒤 각 루프마다 구간을 계산하면 이전 결과를 활용할 수 있어 O(N)이면 해결된다. 이 때 정렬을 해도 원래 위치를 알 수 있어야 하기 때문에 pair를 사용하였다.

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

#define MAX 5000000

int cnt[MAX + 1];

bool compare(pair<int, int>& a, pair<int, int>& b) {
    return a.first > b.first;
}

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer(starts.size());
    
    for (int i = 1; i <= e; i++) {
        for (int j = 1; j * i <= e; j++) {
            cnt[i * j]++;
        }
    }
    
    vector<pair<int, int>> numbers;
    int startSize = starts.size();
    for (int i = 0; i < startSize; i++) {
        int start = starts[i];
        
        numbers.push_back({start, i});
    }
    
    sort(numbers.begin(), numbers.end(), compare);
    
    int manyCnt = -1;
    int many = -1;
    int start = e;
    for (pair<int, int>& number : numbers) {
        int dest = number.first;
        int index = number.second;
        
        for ( ; start >= dest; start--) {
            if (cnt[start] >= manyCnt) {
                many = start;
                manyCnt = cnt[start];
            }
        }
        
        answer[index] = many;
    }
    
    return answer;
}