억억단을 외우자

문제 설명

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

억억단은 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]

---

문제 해설

 

조건항 계산을 진행할 떄, 최솟값을 Start의 [0]번으로 하면 틀린다. 아직도 왜 그렇게 하면 틀리는지는 잘 모르겠으나, 1부터 조건항을 계산해주어야 한다.

 

약수의 공식을 생각해야 한다. 최소로 for문을 돌려서 가장 적게 순환시켜야 한다. 탐색시간과 배열생성시간은 같으나, 배열생성시 굳이 더 탐색할 필요가 없는건 더 탐색하지 말고, 1씩이 아니라 2씩 더해도 무방하다. x와 y축의 값이 같다는걸 생각하자.

 

결과를 측정할 때, 역순으로 전체순환을 진행하면서, 현재값과 현재 가장 최대로 중첩된 값을 계산하여, 현재 값이 더 크거나 같을경우 현재 숫자가 작으면서 중첩된 갯수가 많은 숫자를 갱신하고 집어넣어주면 된다.

---

첫 번째 시도

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer;
    vector<int> CountVector;

    sort(starts.begin(), starts.end());
    CountVector.resize(e+1);

    for (int i = starts[0]; i <= e; i++) 
    {
        int nowcount = i;
        int max = pow(nowcount, 2);
        while(nowcount < max) {
            if (nowcount <= e)
                CountVector[nowcount] += 2;
            else break;
            nowcount += i;
        }
        if (nowcount <= e)
            CountVector[max]++;
    }

    for (auto& number : starts)
    {
        vector<int>::iterator nowMax = max_element(CountVector.begin() + number, CountVector.end());
        answer.push_back(nowMax - CountVector.begin());
    }
    return answer;
}

실패

 

객체값에 대해, 순환으로 정리한것까지는 좋았으나, 시작하는 값이 1이되어야 한다. starts[0]번으로 배열을 생성하면 무조건 틀린다.

 

또한, 객체를 탐색하고 결과물을 도출할 때, 이미 검사한걸 또 검사하게 되면 시간초과가 나타난다.

 

한번 검사한건 다시 검사하지 않도록 예외처리를 할 수 있도록 하자.

 

---

두 번째 시도

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer;
    vector<int> CountVector;

    CountVector.resize(e + 1);

    for (int i = 2; i <= e; ++i)
        for (int j = 1; j <= min(e / i, i - 1); ++j)
            CountVector[i * j] += 2;
    for (int i = 1; i <= sqrt(e); ++i)
        CountVector[i * i] += 1;

    for (auto& number : starts)
        answer.emplace_back(max_element(CountVector.begin() + number, CountVector.end()) - CountVector.begin());

    return answer;
}

실패

 

객체의 순환값을 1부터 시작하여, 가능한 적은 탐색횟수로 탐색하게 하였다.

 

그러나, max_element로 인하여, 전체순환을 진행하기 때문에, 이미 한번 탐색한 구간을 다시 탐색하게 되어 시간초과가 나타난다.

 

---

세 번째 시도

#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer;
    vector<int> CountVector;
    vector<int> ChackKey;

    CountVector.resize(e + 1);
    ChackKey.resize(e + 1);
    for (int i = 2; i <= e; ++i)
        for (int j = 1; j <= min(e / i, i - 1); ++j)
            CountVector[i * j] += 2;

    for (int i = 1; i <= sqrt(e); ++i)
        CountVector[i * i] += 1;

    int nowmax = CountVector.back();
    int nowNumber = e;
    for (int i = e; i >= 1; --i) {
        if (CountVector[i] >= nowmax)
        {
            nowmax = CountVector[i];
            nowNumber = i;
        }
        ChackKey[i] = nowNumber;
    }

    for (auto& number : starts)
        answer.emplace_back(ChackKey[number]);

    return answer;
}

성공

 

전체 순환을 진행하고, 객체의 탐색시, nowmax와 nowNumber를 갱신하면서, 역순으로 순환. 역순으로 순환한 결과가 CountVector[i]에 대해 현재 가장 많이 중첩되었거나 같은지 확인하여, 숫자를 갱신해준다.

 

마지막에 starts의 탐색은 O(N)이 되게 탐색시간을 줄일 수 있었다.