정수로 이루어진 배열이 주어지고, 모든 요소는 1,000,000 미만이라고 가정합니다. 이 문제의 목표는 배열에 포함된 소수 중 가장 큰 소수와 가장 작은 소수를 찾아 그 차이를 계산하는 것입니다.
문제 설명
배열의 각 요소가 소수인지 판별한 뒤, 소수들 사이의 최댓값과 최솟값을 구하고 두 값의 차를 반환하면 됩니다. 단순히 매번 소수 여부를 검사하는 방식도 가능하지만, 배열의 크기가 커질 경우 비효율적일 수 있습니다.
예시
배열: [ 1, 2, 3, 4, 5 ] 가장 큰 소수 = 5 가장 작은 소수 = 2 차이 = 5 - 2 = 3
해결 접근 방법
이 문제는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하면 효율적으로 해결할 수 있습니다. 에라토스테네스의 체는 주어진 숫자보다 작은 모든 소수를 한 번에 빠르게 찾아낼 수 있는 고전적인 방법으로, 시간 복잡도는 O(N log log N)입니다.
동작 과정은 다음과 같습니다.
- 2부터 MAX(1,000,000)까지의 범위에 대해 소수 여부를 미리 계산하여 불리언 배열에 저장합니다.
- 입력 배열의 각 요소를 순회하면서 해당 값이 소수인지 O(1) 시간에 확인합니다.
- 소수인 요소들 중 최댓값과 최솟값을 갱신합니다.
- 최댓값에서 최솟값을 뺀 결과를 반환합니다.
Java 구현 예제
다음은 위 접근 방식을 Java로 구현한 전체 코드입니다.
public class JavaTester {
static int MAX = 1000000;
static boolean prime[] = new boolean[MAX + 1];
public static void runSieveOfEratosthenes(){
// 모든 플래그를 true(소수 후보)로 초기화
for(int i=0; i< MAX+1; i++) prime[i] = true;
// 1은 소수가 아니므로 false 처리
prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
// prime[p]가 아직 변경되지 않았다면 p는 소수
if (prime[p]) {
// p의 배수들을 모두 소수가 아닌 것으로 표시
for (int i = p * 2; i <= MAX; i += p) prime[i] = false;
}
}
}
public static int difference(int arr[]){
int min = MAX + 2;
int max = -1;
for (int i = 0; i < arr.length; i++) {
// 해당 숫자가 소수인지 확인
if (prime[arr[i]] == true) {
// 최댓값과 최솟값 갱신
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
}
return max - min;
}
public static void main(String args[]){
// 체(Sieve) 실행
runSieveOfEratosthenes();
int arr[] = { 1, 2, 3, 4, 5 };
System.out.println(difference(arr));
}
}실행 결과
3
코드 설명
- runSieveOfEratosthenes(): 2부터 √MAX까지의 수 p에 대해, p가 소수라면 p의 배수를 모두 제거하는 방식으로 소수 테이블을 완성합니다.
- difference(): 배열을 한 번만 순회하며 소수인 요소의 최댓값(max)과 최솟값(min)을 추적한 뒤, 두 값의 차이를 반환합니다.
이처럼 에라토스테네스의 체를 미리 구성해 두면, 배열의 크기가 매우 크더라도 각 요소의 소수 판별을 상수 시간에 처리할 수 있어 전체 성능이 크게 향상됩니다.