백준 - 투 포인터 1644번 소수의 연속함 / 문제풀이, 오답노트, 에라토스테네스의 체 알고리즘

 

에라토스테네스의 체 알고리즘을 알고 있어야 해결할 수 있는 문제였다.

이 알고리즘만 확실하게 알면 어렵지 않게 풀 수 있다.

난 이 알고리즘을 몰랐기 때문에 시간 초과로 틀렸다.

알고리즘에 대한 자세한 설명은 여기 글에 적어놨다.

https://byungil.tistory.com/197

에라토스테네스의 체 알고리즘 - 소수 구하기 알고리즘

 

= 접근 방법 ( 틀린 이유 ) =

 

내가 처음 접근한 소수 찾는 코드

 
int n = Integer.parseInt(br.readLine());
List<Integer> list = new ArrayList<>();
        int count = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= i; j++) {
                if (i % j == 0) {
                    count++;
                }
            }
            if (count == 1) {
                list.add(i);
            }
            count = 0;
        }

처음에 소수 찾는 방법도 생각하지 못했기 때문에 이러한 소수 찾는 코드를 구글링 후 해결했다.

결국은 시간초과

시간 복잡도 => O(N^2)

 

주어진 제한 시간에 통과하려면 에라토스테네스의 체 알고리즘을 사용해서 소수를 구해야 된다.

시간 복잡도 => O(Nlog(logN))

 

= 문제 해결 = 

 

1. 소수 구하기.

2. 소수의 연속 합으로 주어진 정수를 구할 수 있는지 판단하기.

 

에라토스테네스의 체 알고리즘을 이용해서 소수를 구하고

 

투 포인터에서 우리가 그동안 계속 풀어왔던 부분합을 이용해서 해결하면 끝!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 1. input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        int[] arr = new int[n + 1];
 
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }
 
        // 2. 소수인지 아닌지 판별 ( 1은 소수가 아니다 )
        // 어떻게 판별할 수 있을까..?
        // 2로 나누었을 때, 나머지 1, 그럼 15같은 수는 어떻게 해결?
        // 에라토스테네스의 체 알고리즘을 이용하자
        for (int i = 2; i <= n; i++) {
            if (arr[i] == 0) {
                continue;
            }
            for (int j = i + i; j <= n; j+=i) {
                arr[j] = 0;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (i != 0) {
                list.add(i);
            }
        }
 
 
        // 3. 소수가 아니라면 부분합을 이용해서 더함 (getNum 메서드)
        int count = getNum(list, n);
        System.out.println(count);
 
    }
 
    public static int getNum(List<Integer> list, int n) {
        int start = 0; // 시작
        int end = 0; // 끝
        int sum = 0;
        int count = 0;
        while (true) {
            if (sum >= n) {
                if (sum == n) {
                    count++;
                }
                sum -= list.get(start++);
            } else if (end == list.size()) {
                break;
            } else if (sum < n) {
                sum += list.get(end++);
            }
        }
        return count;
    }
}