문제 설명
n개의 정수로 이루어진 배열 A가 있다고 가정해 봅시다. 우리는 배열 안에서 소수인 원소 K를 찾아야 하며, 가능한 모든 후보 K 중에서 A[i] mod K의 값이 최대가 되도록 해야 합니다. 만약 조건을 만족하는 수를 찾지 못하면 -1을 반환합니다.
예를 들어, A = [2, 10, 15, 7, 6, 8, 13]일 때 출력은 13입니다. 배열에는 2, 7, 13이라는 세 개의 소수가 존재하며, 각 소수에 대한 나머지 연산의 최댓값은 다음과 같습니다.
- K = 2일 때: 15 mod 2 = 1
- K = 7일 때: 6 mod 7 = 6
- K = 13일 때: 10 mod 13 = 10
따라서 13이 나머지 값을 가장 크게 만드는 소수입니다.
접근 방법
A[i] mod K의 값을 최대화하려면 K는 반드시 배열에서 가장 큰 소수여야 하고, A[i]는 K보다 작은 원소들 중 가장 큰 값이어야 합니다. 즉, 문제는 단순히 배열 내에서 최댓값인 소수를 찾는 것으로 환원됩니다.
효율적으로 소수를 판별하기 위해 에라토스테네스의 체(Sieve of Eratosthenes)를 활용할 수 있습니다. 먼저 배열의 최댓값 이하의 모든 소수를 체로 구한 뒤, 배열의 원소 중 해당하는 소수를 찾아 그중 최댓값을 반환하면 됩니다. 만약 배열에 소수가 하나도 없다면 -1을 반환합니다.
알고리즘 단계
- 배열의 최댓값 max_elem을 구합니다.
- 0부터 max_elem까지의 범위에서 에라토스테네스의 체를 사용해 소수 여부를 표시합니다.
- 배열을 순회하면서 소수인 원소만 골라 그중 최댓값을 찾습니다.
- 소수가 없으면 -1을 반환하고, 있으면 해당 최댓값을 출력합니다.
C++ 구현 예제
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int getMaxPrime(int arr[], int n) {
int max_elem = *max_element(arr, arr + n);
vector<bool> prime_vals(max_elem + 1, true);
prime_vals[0] = false;
prime_vals[1] = false;
for (int p = 2; p * p <= max_elem; p++) {
if (prime_vals[p] == true) {
for (int i = p * 2; i <= max_elem; i += p)
prime_vals[i] = false;
}
}
int maximum = -1;
for (int i = 0; i < n; i++) {
if (prime_vals[arr[i]])
maximum = max(maximum, arr[i]);
}
return maximum;
}
int main() {
int arr[] = { 2, 10, 15, 7, 6, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max prime is: " << getMaxPrime(arr, n);
}출력 결과
Max prime is: 13
복잡도 분석
에라토스테네스의 체를 구성하는 데 O(M log log M)의 시간이 걸리며(M은 배열의 최댓값), 배열 순회에는 O(N)이 소요됩니다. 전체 시간 복잡도는 O(M log log M + N)이며, 공간 복잡도는 소수 표현 배열을 위해 O(M)입니다.