Overview
CountSemiprimes
특정 구간에서, 두 소수의 곱으로 만들어지는 SemiPrime의 수를 구하라
Solution
SemiPrime들을 구한 뒤, 각 구간의 SemiPrime 수를 모두 저장한다.
#include <vector>
#include <algorithm>
vector<int> solution(int N, vector<int> &P, vector<int> &Q)
{
std::vector<bool> isPrime(N + 1, true);
for(int i = 2 ; (i * i) <= N ; ++i)
{
if(isPrime[i])
{
for(int j = i * i ; j <= N ; j += i)
isPrime[j]=false;
}
}
std::vector<int> prime{};
for(int i = 2 ; i <= N ; ++i)
{
if(isPrime[i])
prime.push_back(i);
}
std::vector<int> semiPrime(N + 1, 0);
for(int i = 0 ; i < prime.size() - 1 ; ++i)
{
for(int j = i ; j < prime.size() ; ++j)
{
if(prime[i] * prime[j] > N)
break;
semiPrime[prime[i] * prime[j]] = 1;
}
}
for(int i = 1 ; i <= N ; ++i)
semiPrime[i] += semiPrime[i - 1];
vector<int> result{};
for(int i = 0 ; i < P.size() ; ++i)
result.push_back(semiPrime[Q[i]] - semiPrime[P[i] - 1]);
return result;
}
Error
모든 SemiPrime을 직접 구하지 않는 풀이도 있는 것 같지만 설명없이는 이해하기 힘든 점 + 그냥 다 구해도 Performance Test를 통과하는 사례가 많아서 그냥 구현했는데, 왠지 모르게 Large Case에서 프로그램이 터져버린다..
다른 언어에서는 N + 1크기 배열 2개 그냥 선언해서 사용하던데, 시스템 문제인지 유저 문제인지 잘 모르겠다 :(
그리고 구간의 SemiPrime 등장 횟수를 기록해두는 것이 중요한데, Time Over의 원인을 SemiPrime을 구하는 곳이라고 생각하여 굉장히 시간 낭비를 많이 해버렸다.
다양한 방법으로 SemiPrime의 등장 횟수를 구하던데, 꽤 오래봐도 이해가 안가더라…
CountNonDivisible
배열 내 원소들이 다른 원소들로 나누어지는 지 확인하라.
Failure
에라토스테네스의 체와 비슷하게, 각 원소와 그의 배수에 등장 횟수를 기록하였으나 O(N ** 2)의 시간 복잡도로 Performance Test를 통과하지 못했다.
Solution
매 원소마다 모든 원소를 살펴볼 필요없이, 각 원소의 등장 횟수만 기록한 뒤 10-1, 10-2에서 사용한 것 처럼 인수를 찾아나간다.
#include <algorithm>
vector<int> solution(vector<int> &A)
{
auto N = A.size();
std::vector<int> count(2 * N + 1, 0);
for(const auto &a : A)
++count[a];
std::vector<int> result{};
for(const auto &a : A)
{
int divisor{0};
for(int i = 1 ; i * i <= a ; ++i)
{
if(a % i == 0)
{
divisor += count[i];
if(a / i != i)
divisor += count[a / i];
}
}
result.push_back(N - divisor);
}
return result;
}