[프로그래머스] 소수 찾기 (Java)

[프로그래머스] 소수 찾기 (Java)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12921

풀이/후기

1부터 n까지라는 것을 보고 dp로 풀 수 있지 않을까? 하고 dp로 풀었다.

소수일 때마다 카운트를 하는 것과 성능차이가 날지 궁금해서 풀어보니 확실히 속도는 dp가 빨랐다.

 

이 문제에서 큰 효율을 본 것은 아니지만...!

예전엔 dp너무 어려워서 엉엉 울었는데,,

이제는 활용 방안을 생각해 낼 수 있어서 뿌듯했다.

왼 - dp 오 - 카운트

 

코드

dp로 푼 풀이

class Solution {
    public int solution(int n) {
        int[] dp = new int[n+1];
        
        dp[1] = 0;
        dp[2] = 1;
        
        for (int i=3; i<=n; i++){
            if (isPrime(i)){
                dp[i] = dp[i-1] + 1;
            } else dp[i] = dp[i-1];
        }
        
        return dp[n];
    }
    
    static boolean isPrime(int num){
        int sq = (int) Math.sqrt(num);
        for (int i=2; i <= sq; i++){
            if (num % i == 0) return false;
        }
        return true;
    }
}

 

카운트로 푼 풀이

class Solution {
    public int solution(int n) {
        int answer = 1; // 2
        
        for (int i=3; i<=n; i++){
            if (isPrime(i)){
                answer++;
            }
        }
        
        return answer;
    }
    
    static boolean isPrime(int num){
        int sq = (int) Math.sqrt(num);
        for (int i=2; i <= sq; i++){
            if (num % i == 0) return false;
        }
        return true;
    }
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/1/12921.%E2%80%85%EC%86%8C%EC%88%98%E2%80%85%EC%B0%BE%EA%B8%B0/%EC%86%8C%EC%88%98%E2%80%85%EC%B0%BE%EA%B8%B0.java

참고