위의 문제는 약수의 개수 구하기가 핵심인 문제이다.
시간 복잡도에 굉장히 민감한 문제였기 때문에,
어떻게 시간을 줄일지 많은 고민이 필요했다.
그래서 이렇게 글로 정리하며 고민해보기로 결심했다.
간단하지만 복잡한, O(N^2)
간단히, 아주 간단히 생각 했을 때 O(N^2)의 복잡도로 구할 수 있다.
2중 for문을 사용하는 코드이기 때문에, O(N^2)의 복잡도를 가진다.
그냥 루트 e까지 무작정 나누어 떨어지는 값마다 카운트를 한다.
약수를 이렇게 무작정 구하니, 당연히 시간초과가 발생했다.
vector<int> solution(int e, vector<int> starts) {
vector<int> answer;
vector<int> divisors(e + 1);
divisors[1] = 1;
for (int i = 2; i <= e; i++) {
int cnt = 0;
for (int j = 1; j <= sqrt(i); j++) {
if(i % j == 0)
cnt++;
}
divisors.push_back(cnt);
} // 말도 안되는 O(N^2)의 Logic
for (auto i : starts)
answer.push_back(max_element(divisors.begin() + i, divisors.begin() + e) - divisors.begin());
return answer;
}같은 N(O^2), 다른 느낌
약수를 구하는 로직을 조금 변경했다.
에라토스테네스의 체를 거꾸로 하는 느낌의 로직이다.
앞으로 나아가며 해당 수의 배수 위치에만 +1을 해준다.
하지만 이 로직 또한 시간초과가 발생했다.
약수를 구하는 것이 아닌, 최대값을 구하는 것이 문제였던 것이다.
vector<int> solution(int e, vector<int> starts) {
vector<int> answer;
vector<int> divisors(e + 1);
for (int i = 1; i <= e; i++) {
for (int j = i; j <= e; j += i) {
divisors[j] += 1;
} // i의 배수마다 divisors에 1을 더함
} // 같은 O(N^2)이지만 시간이 훨씬 줄어든다.
for (auto i : starts)
answer.push_back(max_element(divisors.begin() + i, divisors.begin() + e) - divisors.begin());
// 이 부분이 문제가 되는 로직이다.
// O(N)을 starts 배열 길이 만큼 돌림.
return answer;
}문제는 Index
결국 문제는 최대값이 위치한 Index를 구하는 방식이었다.
원래는 C++의 내장 함수인 max_element()를 사용했었다.
하지만 해당 함수 자체로 O(N)의 복잡도를 가지기 때문에,
for문 내에서 돌아가게 되면 또 O(N^2)의 복잡도를 가지게 되어 시간초과가 난다.
따라서, 방법을 바꾸어 O(N)만에 최대 index를 구해낼 수 있도록 한다.
뒤에서 부터 배열을 훑으며 최대 값을 저장하며 나아가는 방식이다.
vector<int> solution(int e, vector<int> starts) {
vector<int> answer;
vector<int> divisors(e + 1);
vector<int> maxvec(e + 1); // 최대값 배열을 만듬
int max = 0, max_idx = 0;
for (int i = 1; i <= e; i++) {
for (int j = i; j <= e; j += i) {
divisors[j] += 1;
}
}
for (int i = e; i >= 0; i--) {
max_idx = max > divisors[i] ? max_idx : i;
max = max > divisors[i] ? max : divisors[i];
maxvec[i] = max_idx;
}
// 최대값 배열에 구간의 최대값을 저장하며 나아간다.
// 마지막엔 해당 구간 참조만 하면 됨.
for (auto i : starts)
answer.push_back(maxvec[i]);
return answer;
}