Leetcode - 202. Count Primes

[Must do question series-easy]

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

 

Count Primes - LeetCode

---

문제

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10

Output: 4

Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

---

prime number - 소수 찾기이다.

소수란 1과 자기자신만을 약수로 가지는(나누어 떨어지는) 수이다.

 

양수인 n 이 주어지고 n 보다 작은 수 중에 소수의 갯수를 구하면 된다.

 

일단 무식하게 풀어본다. for 문을 돌면서 하나라도 나누어 떨어지는 수는 소수가 아니기 때문에 제외하는 방식으로 구현해본다.

class Solution {
    public int countPrimes(int n) {
        int answer = 0;
        if(n==2){
            return 0;
        }
        for(int i = 2 ; i < n ; i++){
            if(isPrime(i) == true){
                answer++;
            }
        }
        return answer;  
    }
    public boolean isPrime(int n){
        if(n==2){
            return true;
        }
        for(int i = 2 ; i < n ; i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
}

확실히 루프를 두번 쓰니 n은 499979 에서 Time Limit Exceeded 가 뜬다.

 

이제 조금씩 런타임을 줄여보자. 소수를 찾는 방법이 현재는 2부터 자가자신-1 까지 전부 나눠보며 나누어 떨어지는게 없으면 소수라고 판단한다. 이 루프를 없애려면 다른 소수를 찾는 방법이 필요한 것 같다.

 

 

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

2의 배수 빼고

1 2 3 5 7 9 11 13 15 17 19 21 23 25

3의 배수 빼고

1 2 3 5 7 11 13 17 19 23 25

5의 배수 빼고 

1 2 3 5 7 11 13 17 19 23 

7의 배수 빼고

...

11의 배수 빼고...

 

소수의 배수들을 빼면 되는것 같다.

import java.util.*;
class Solution {
    
    ArrayList<Integer> arrayList = new ArrayList();
    public int countPrimes(int n) {
        int answer = 0;
        
        if(n==2){
            return 0;
        }
        // 1 - 일단 전체 arrayList 를 만든다.
        for(int i = 2 ; i < n ; i++){
            arrayList.add(i);
        }
        
        //문제점 : 2의 배수만 없어지고 있다.
        //2의 배수를 없애고 나선 다음걸 없애야 되는데 break 때문인건가
        for(int i = 0 ; i < arrayList.size() ; i++){
            // 2 - arrayList의 i 번째 항목이 소수라면 
            // 2 가 제일 먼저 선택된다. 그럼 2의 배수를 없앤다.
            if(isPrime(arrayList.get(i)) == true){
                // 2 - arrayList의 i번째 항목이 소수라면
                removeAllMultipleNumber(arrayList.get(i));
                // break;
            }
        }
  
        //debug
        // for(int primeNumber : arrayList){
        //     System.out.println(primeNumber);
        // }
        answer = arrayList.size();
    
        
        return answer;  
    }
    public void removeAllMultipleNumber(int n){
        // 3 - arrayList 중 n 의 배수들은 다 없앤다.
        //먼저 자기자신 빼고 2의 배수들이 다 제외된다.
        for(int i = 0 ; i < arrayList.size() ;i++){
            // 4 - arrayList.get(i)가 n 의 배수이면 없앤다.
            if(isAMultipleOfB(arrayList.get(i) , n)){
                // 2 자기자신 빼고 2의 배수들을 다 없앤다.
                // System.out.println("removed item : " + arrayList.get(i));
                arrayList.remove(i);
            }
        }
    }
    public boolean isAMultipleOfB(int a, int b){
        if(a==b){
            //자기 자신일때는 빼지 않는다.
            return false;
        }
        if(a%b==0){
            return true;
        }else{
            return false;
        }
    }
    
    public boolean isPrime(int n){
        if(n==1){
            return false;
        }
        if(n==2){
            return true;
        }
        for(int i = 2 ; i < n ; i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
}

arrayList를 loop 하지만 발견되는 prime 의 배수는 제거하기 때문에 한단계의 loop 를 지날 때 마다 비교해야 하는 수는 기하급수적으로 작아질 거라 생각했다. 2만 해도 2의 배수가 천지빽까리 니까... 근데 똑같이 499979에서 Time Limit Exceedded 가 뜬다.

 

 

100000에서 부터 시간 초과가 되니 참 어떻게 해야되지...

 

일단 ArrayList가 나는 LinkedList 형태로 삭제가 용이한 줄 알았는데 Array였다!(이제라도 알아서 다행인건가)

Array는 삭제에 시간이 많이 걸린다. (삭제한 뒷쪽 element 를 다 땡겨야 되기 때문)

그래서 일단 ArrayList 대신 LinkedList 를 사용해 보았다.

 

역쉬 Time Limit Exeeded 가 뜬다.허허허허헣 내 코드는 똥이야 똥!

 

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

코드를 그냥 처음부터 다시 짜보자.

 

에라의 체를 사용하면 되는데 소수의 배수들을 하나씩 지워나가는 방법이다.

 

속도를 위해 ArrayList 쓰지않고 boolean array를 쓰기로 한다.

 

그리고 소수의 배수를 지우는 부분을 2중 루프로 

 

i : 2~array.length

j : 2~array.length 

 

하고 

 

생각해보니 이전 코드가 오래 걸렸던 이유는 소수의 배수를 찾는 부분이였던것 같다.

소수의 배수를 찾는 건 그냥 해당소수*index 를 하면되는건데

왜 배수도 루프를 돌면서 찾게 했을까

 

멍청한놈같으니라구

 

그래서 배수찾는 부분을 for(int j = 2 ; i*j < primeNum.length ; j++) 이런식으로 짰다.

 

그랬더니

 

class Solution {
    public int countPrimes(int n) {
        int answer = 0;
        // n=10 ,, 1부터 9까지의 수 ->  size = 10
        boolean[] primeNum = new boolean[n];
        //init array to true
        for(int i = 0 ; i < primeNum.length ; i++){
            primeNum[i] = true;
        }
        
        if(n == 0 || n==1 || n==2){
            return 0;
        }
    
        //not prime == false
        primeNum[1] = false;
        primeNum[0] = false;
        
        for(int i = 2 ; i <primeNum.length ; i++){
            for(int j = 2 ; i*j < primeNum.length ; j++){
                // System.out.println(i*j);

                primeNum[i*j] = false;
            }
        }
        //count true
        for(boolean bool : primeNum){
            // System.out.println(bool);
            if(bool){
                answer++;
            }
        }
        return answer;
        
    }
}

 

통과

Success

Details 

Runtime: 49 ms, faster than 22.46% of Java online submissions for Count Primes.

Memory Usage: 38.1 MB, less than 5.66% of Java online submissions for Count Primes.

 

 

아니 그럼 빠른 사람은 얼마나 빠르다는 거지

 

빠른년생인가

 

다른 사람의 코드

12 ms Java solution modified from the hint method, beats 99.95% - LeetCode Discuss

publib int countPrimes(int n) {
    if (n < 3)
        return 0;
        
    boolean[] f = new boolean[n];
    //Arrays.fill(f, true); boolean[] are initialed as false by default
    int count = n / 2;
    for (int i = 3; i * i < n; i += 2) {
        if (f[i])
            continue;
        
        for (int j = i * i; j < n; j += 2 * i) {
            if (!f[j]) {
                --count;
                f[j] = true;
            }
        }
    }
    return count;
}

 

이분은 count 소수를 찾는 과정에서 계산해서 하나의 loop 가 빠진것 같다.

 

count 를 n/2 로 초기화 시키고 ... 왜??

 

코드 이해가 안된다. 

 

다른 빠른 답들도 n/2 로 초기화 시키는데 Count all the odd number이라고 하는데

 

아 소수는 2빼고 다 홀수여야 하구나

 

오케이 그리고 3부터 loop를 돌면서 i*i 가 n 보다 작을 때 까지 2씩 increment 해주신다.(홀수만 체킹)

 

그아래 부분은 똑같이 배수를 지워 나가는 부분이다. 

 

에라의 체 + 소수는 2빼고 다 홀수


아이디어인 것 같다. 

 

 

 

끗.