알고리즘 풀이/Java
[알고리즘][X] 소수의 연속합
Dong's Universe
2024. 4. 15. 17:19
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
static int N;
static boolean[] isPrime;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
isPrime = new boolean[N+1];
Arrays.fill(isPrime, true);
eratones_filter();
// 소수 리스트에 넣어주기
List<Integer> prime = new ArrayList<>();
for (int i = 2; i < isPrime.length; i++) {
if (isPrime[i]) {
prime.add(i);
}
}
// 투포인터 이용해서 N이 나오는지 확인
int result = 0;
int start = 0;
int end = 0;
if (prime.isEmpty()) {
System.out.println(0);
return;
}
int sum = prime.get(0);
while (start <= end) {
if (sum == N) {
result++;
end++;
if (end >= prime.size()) {
break;
}
sum += prime.get(end);
} else if (sum < N) {
end++;
if (end >= prime.size()) {
break;
}
sum += prime.get(end);
} else {
sum -= prime.get(start);
start++;
}
}
System.out.println(result);
}
private static void eratones_filter() {
for (int i = 2; i <= (int) Math.sqrt(N); i++) {
if (!isPrime[i]) {
continue;
}
int j = 2;
while (i * j <= N) {
isPrime[i * j] = false;
j++;
}
}
}
}
- 리스트를 활용해서 푼 풀이
- 리스트를 사용하면 0일때의 예외처리가 어려워진다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N;
static boolean[] isPrime;
static int[] prime = new int[283147];
static int primeCnt = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
isPrime = new boolean[N+1];
Arrays.fill(isPrime, true);
eratones_filter();
// 소수 리스트에 넣어주기
for (int i = 2; i < isPrime.length; i++) {
if (isPrime[i]) {
prime[primeCnt++] = i;
}
}
// 투포인터 이용해서 N이 나오는지 확인
int result = 0;
int start = 0;
int end = 0;
int sum = prime[0];
while (end < primeCnt) {
if (sum < N) {
end++;
sum += prime[end];
continue;
}
if (sum == N) {
result++;
}
sum -= prime[start];
start++;
}
System.out.println(result);
}
private static void eratones_filter() {
for (int i = 2; i <= (int) Math.sqrt(N); i++) {
if (!isPrime[i]) {
continue;
}
int j = 2;
while (i * j <= N) {
isPrime[i * j] = false;
j++;
}
}
}
}
- 배열을 이용하면 0일때라도 nullPointerException이 생기진 않는다.
- 또한 end가 사이즈보다 커질 때에도 NullPointerException이 생기지 않는다. 왜냐하면 배열의 크기를 이미 충분하게 잡아놓았기 때문이다.
package boj.solution1644;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N;
static boolean[] isPrime;
static int[] prime = new int[283147];
static int primeCnt = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
isPrime = new boolean[N+1];
Arrays.fill(isPrime, true);
eratones_filter();
// 소수 리스트에 넣어주기
for (int i = 2; i < isPrime.length; i++) {
if (isPrime[i]) {
prime[primeCnt++] = i;
}
}
// 투포인터 이용해서 N이 나오는지 확인
int result = 0;
int start = 0;
int end = 0;
int sum = prime[0];
while (end < primeCnt) {
if (sum > N) {
sum -= prime[start];
start++;
continue;
}
if (sum == N) {
result++;
}
end++;
sum += prime[end];
}
System.out.println(result);
}
private static void eratones_filter() {
for (int i = 2; i <= (int) Math.sqrt(N); i++) {
if (!isPrime[i]) {
continue;
}
int j = 2;
while (i * j <= N) {
isPrime[i * j] = false;
j++;
}
}
}
}
- start를 움직이든지 end를 움직이든지 사실 상관없다!