[알고리즘] BOJ 1644 소수의 연속합 (JAVA)

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

백준 골드3 난이도치고는 문제를 읽었을 때 별로 어렵지 않다 생각했지만, 의외의 부분에서 바로 해결을 못해 조금 시간을 썼던 문제였다.

 

우선 소수 판별이 들어간 문제기 때문에 소수판별=에라토스테네스의 체라는 건 알고리즘 문제를 좀 풀어본 사람들은 다 아는 사실이라

 

에라토스테네스의 체를 사용하여 소수를 찾아내고, 해당 소수들을 저장한 리스트를 투포인터 탐색을 했다.

 

하지만 에라토스테네스의 체를 사용한 게 무색하게 시간초과가 아닌 메모리 초과가 발생해서 당황했는데,

 

아이디어 자체 문제가 아닌 구현 과정에서 사용한 자료구조에 문제가 있었다.

 

에라토스테네스의 체 알고리즘을 사용하기 위해선 소수의 배수를 걸러내는 작업이 필요하다.

 

해당 작업을 빠르게 수행하기 위해 N 이하인 소수의 배수들을 전부 HashSet에 저장하여 필터링하는 로직을 구현했는데

 

HashSet의 특성상 탐색 과정에서의 시간복잡도가 O(1)이라는 매우 큰 장점은 있지만

 

hash라는 것의 특성상 각각의 값을 해쉬값을 통해 구별짓고, 그렇다 보니 해쉬값까지 별도로 저장이 필요하여

 

오히려 N이 커질수록 리스트나 배열에 비해 잡아먹는 메모리가 커진다는 점을 놓쳐서 조금 헤맸던 문제였다.

 

기존의 HashSet을 통해 소수가 아닌 수를 저장하여 가져오는 방식 대신,

 

단순히 N크기만큼의 boolean 배열을 통해 저장하고, 비교하는 것만으로도 메모리 문제는 해결이 되었다.

 

 

 

import java.io.*;

import java.util.*;

import java.io.*;

import java.util.*;

public class boj1644 {

    static int N, idx, cnt;

    static List<Integer> prime;

    //해쉬는 해쉬값을 사용하여 데이터값을 구별저장하기 때문에,

    //탐색 과정에서 시간적인 이득을 볼 순 있지만 해쉬값 저장을 하다보니 메모리 사용량이 많아진다!!

    // static HashSet<Integer> notPrime;

    static boolean isPrime[];

    public static void twoPointer() {

        int l, r, sum;

       

        if (N == 1) {

            cnt = 0;

            return;

        }

        l = 0;

        r = 0;

        sum = prime.get(0);

        while (l <= r) {

            if (r >= prime.size()) {

                if (sum > N) {

                    sum -= prime.get(l);

                    l++;

                    continue;

                }

                return;

            }

            if (sum > N) {

                sum -= prime.get(l);

                l++;

            }

            else {

                if (sum == N) {

                    cnt++;

                }

                r++;

                if (r < prime.size()) {

                    sum += prime.get(r);

                }

            }

        }

    }

    public static void pre() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        prime = new ArrayList<>();

        // notPrime = new HashSet<>();

        isPrime = new boolean[N + 1];

        Arrays.fill(isPrime, true);

       

        // notPrime.add(1);

        isPrime[1] = false;

        cnt = 0;

        // 에라토스테네스의 체

        for (int i = 2; i <= N; i++) {

            // if (notPrime.contains(i)) {

            //     continue;

            // }

            if (!isPrime[i]) {

                continue;

            }

            prime.add(i);

            for (int j = 2; i * j <= N; j++) {

                isPrime[i * j] = false;

            }

        }

    }

    public static void main(String args[]) throws IOException {

        pre();

        twoPointer();

        System.out.println(cnt);

    }

}

 

 

실행 시간은 다음과 같다. 참고로 IndexOutOfBounds 에러는 채점 99%쯤 가서 나와서

 

처음에 채점 90%를 넘어갈때쯤엔 맞았겠구나 했는데, 범위를 벗어나는 에러가 날 수가 없는데 발행해서

 

조금만 생각을 해보니 1을 처리해주지 않아서 prime 리스트에서 접근할 수 없어서 나는 에러였다.

 

 

HashSet, HashMap이 무조건 좋은점만 있는건 아니라는 걸 다시금 깨닫게 된 문제였다.