백준 알고리즘 2581번 문제풀이(JAVA)

소수 구하는 문제는 자주 나오기 때문에 익혀두면 편하다. 소수 구하는 방법으로는

 

1. for문으로 N까지 확인하여 구하기

2. for문으로 sqrt(N)까지 확인하여 구하기

3. 에라토스테네스의 체 이용하여 구하기

 

이렇게 총 3가지로 크게 나뉜다.

 

3가지 방법 중에서 가장 효율적인 에라토스테네스의 체를 이용하여 문제를 해결했다.

 

처음 내가 작성하여 맞은 코드다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

        boolean[] isNotPrime = new boolean[10001];

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        isNotPrime[0] = true;
        isNotPrime[1] = true;

        for(int i = 2;i<Math.sqrt(N);i++) {
            for(int j = i*i; j< N + 1; j = j+i){
                isNotPrime[j] = true; // 소수가 아님
            }
        }

        int sum = 0;
        int min = 0;
        for(int i = M;i<N+1;i++) {
            if(min == 0) {
                if(!isNotPrime[i]){
                    sum += i;
                    min = i;
                }
            }else {
                if(!isNotPrime[i]){
                    sum += i;
                }
            }
        }

        if(sum == 0){
            System.out.println(-1);
        }else {
            System.out.println(sum);
            System.out.println(min);
        }
    }
}

 

M과 N 사이의 소수를 구하는 문제라 범위가 정해져 있지만, 에라토스테네스의 체를 이용하면 처음부터 N까지 소수를 구한 뒤 합계와 최솟값을 구해도 전혀 문제가 없다. 사실 주어진 범위 내의 수들만 체크해서 소수를 구해야하는 거 아닌가 라는 생각에 고민에 조금 빠졌었는데, 오히려 중간부터 구할려니 소수인지 아닌지 추가적으로 나머지값을 통해 반복문을 가지고 또 판별해줘야해서 오히려 더 비효율적이다.

 

위 코드를 클린 코드로 다시 짜보았다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static boolean[] isNotPrime = new boolean[10001];

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        isNotPrime[0] = true;
        isNotPrime[1] = true;

        isCheckPrime(N); 

        int sum = getSum(M,N);
        int min = getMin(M,N);

        printSumAndMin(sum, min);

    }

    public static void isCheckPrime(int end) {
        for(int i = 2;i<Math.sqrt(end);i++) {
            for(int j = i*i; j< end + 1; j = j+i){
                isNotPrime[j] = true; // 소수가 아님
            }
        }
    }

    public static int getSum(int start, int end) {
        int sum = 0;

        for(int i = start;i<end+1;i++) {
            if(!isNotPrime[i]){
                sum += i;
            }
        }

        return sum;
    }

    public static int getMin(int start, int end) {
        int min = 0;
        for(int i = start; i < end+1; i++) {
            if(!isNotPrime[i]) {
                min = i;
                break;
            }
        }

        return min;
    }

    public static void printSumAndMin(int sum, int min) {

        if(sum == 0){
            System.out.println(-1);
        }else {
            System.out.println(sum);
            System.out.println(min);
        }

    }
}

 

기능마다 함수로 구현해 함수는 하나의 기능만을 수행할 수 있도록 하고, 매개인자나 함수명도 누가봐도 어떤 걸 의미하는지 알 수 있도록 지었다. 확실히 이렇게 클린 코드로 정리하니까 한 눈에 들어와 이해하기도 쉽고 효율적인 것 같다.

 

아래 제출이 첫번째 작성한 코드이고 위 제출이 클린 코드이다. 클린 코드로 작성한 코드가 더 긴데도 불구하고 메모리와 시간은 얼마 차이 안나긴 하지만 더 적게 든다. 이건 단순 알고리즘 문제라 성능 차이가 크게 나지 않지만 실제로 프로그램을 구현하거나 큰 규모의 작업을 진행할 땐 어마어마한 차이를 보일 거 같다. 앞으로 알고리즘 문제를 풀 때도 이렇게 클린 코드로 작성하는 훈련을 계속해야겠다.