lango

찍먹? 부먹?
난 부먹 개발자.

3 minute read


Input-1
10
Output-1
4

Input-2
5
Output-2
3

문제 풀이

먼저 n까지의 수 중 소수를 찾아야 한다.

소수란? 2, 3, 5, 7, 11, 13, 17 …
약수가 1과 자신 뿐인 수이다.

어떻게 소수를 구할 수 있을까?

n까지의 수중에서 n보다 작은 수를 나눠지는 수가 있다면 소수가 아니다.
즉, 어떤 수의 배수이면 소수가 아니라는 것이다.

여기까지 이해하였으면 무작정 코딩을 시작해보자. 

1
2
3
4
5
6
7
8
9
10
11
12
13

int i=2; // 소수가 아닌 0과 1을 제외한 n까지의 수
while(i<=n) {
    boolean isPrime = true;
    for(int x=2; x<i; x++) {
        if(i % x == 0) { // 소수 X
            isPrime = false;
            break;
        }
        continue;
    }
    if(isPrime == true) answer++;
    i++;
}

바깥의 while문을 통해 2부터 n까지 순회하는데
안쪽의 for문을 통해 i별로 x를 i로 나눠지는 수가 있다면 소수가 아니다.
또한 소수가 아니라면 반복문의 끝까지 순회할 필요가 없고 수행시간이 오래 걸리기에 break문을 추가하였다.

이때 n값을 50000으로 부여하여 코드를 실행해보니 수행시간은 약 150 밀리초가 소요되었다.
그리고 테스트케이스 11, 12에서 시간초과 문제가 발생하였다.

수행시간을 줄이는 방법은?

이제 어떠한 로직으로 접근하여 수행시간을 최소화할 수 있는지 생각해 보아야 한다.

먼저 n보다 작은 수의 소수들로만 나누어보면 어떨까?
prime(리스트)에 소수를 넣어두고 2부터 n까지 순회하며 i별로 prime의 원소와 나누어지는 지를 검증해보자.

1
2
3
4
5
6
7
8

ArrayList<Integer> prime = new ArrayList<>(); // 소수를 관리할 리스트
prime.add(2);
for(int i=2; i<=n; i++) {
    for(int j=0; j<prime.size(); j++) {
        if(i % prime.get(j) == 0) break;
        if(j+1 == prime.size()) prime.add(i);
    }
}

위와 같이 안쪽 반복문을 통해 n까지의 수중에서 소수들로만 나누어 떨어지면 break하여 불필요한 반복을 줄일 수 있다.

이때도 동일하게 n을 50000으로 실행해보았고 수행시간은 첫번째 풀이의 절반정도인 70 밀리초 정도 소요되었다.
하지만 이번 풀이도 테스트케이스 11에서 시간초과가 발생하였다.

에라토스테네스의 체를 활용한 풀이

소수를 찾는 방법중 잘 알려져 있는 에라토스테네스의 체 방식을 활용해 풀어보자.

에라토스테네스의 체 알고리즘 n이 100이라고 하면 2부터 100까지를 배열에 담은 후 소수가 아닌 것들을 마킹하여 마킹이 안된 수들인 소수를 판별하는 알고리즘이다.

이 알고리즘을 구현하며 중요하게 생각해야 할 것은 앞에서도 언급했지만 바로 불필요한 반복을 줄이는 것이다!
배열에 담아두고 소수가 아닌 수를 마킹할 때 모든 수를 다 순회하며 마킹할 필요없이 마킹할 수의 제곱근 만큼만 반복하는 것이다.
또한 마킹된 수의 배수는 이미 마킹한 것으로 판단하고 검증하지 않도록 구현하면 된다.

에라토스테네스의 체 알고리즘을 활용한 코드는 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

boolean[] arr = new boolean[n+1]; // 소수가 아니면 true, 소수일 경우 false
arr[0] = arr[1] = true; // 0, 1은 소수가 아니기에 true

// 제곱근까지만 반복하며 중첩반목문을 통해 n의 배수에서 소수가 아닌 수를 검증
for(int i=2; i<=Math.sqrt(n); i++) { 
    for(int j=i+i; j<arr.length; j+=i) {
        arr[j] = true;
    }
}

int answer = 0;
for(boolean res : arr) {
    if(res == false) answer++; // 소수의 개수
}

2부터 n의 제곱근까지만 순회(i)하며 i마다 j는 i+i부터 시작해서 i만큼 더하며 n+1만큼 담은 배열의 길이만큼 돌며 소수가 아닌 수를 마킹한다. 

1
2
3
4

// n = 10
// arr: 0,1,2,3,4,5,6,7,8,9,10
i가 2일 때 j는 i+i인 4부터 시작하여 4, 6, 8, 10 수를 돌며 마킹한다.
i가 3일 때 j는 i+i인 6부터 시작하여 6, 9 수를 돌며 마킹한다.

에라토스테네스의 체를 통해 작성한 코드를 실행하니 7 밀리초 정도로 대폭 줄어든 것을 확인할 수 있었고 문제 채점도 통과할 수 있었다.


작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long start = System.currentTimeMillis();
        solution(n);
        long end = System.currentTimeMillis();
        System.out.println("수행시간 = " + (end-start));
    }
    
    public static int solution3(int n) {        
        boolean[] arr = new boolean[n+1];
        arr[0] = arr[1] = true;
        for(int i=2; i<=Math.sqrt(n); i++) {
            for(int j=i+i; j<arr.length; j+=i) {
                arr[j] = true;
            }
        }
        int answer = 0;
        for(boolean res : arr) {
            if(res == false) answer++;
        }
        return answer;
    }
}

회고

  • 단순히 소수를 찾는 로직은 어렵지 않았으나 소수를 찾는 시간을 줄이는 것을 핵심으로 고민하는 과정에서 에라토스테네스의 체 알고리즘을 공부할 수 있었다.

You may also enjoy