프로그래머스_소수 찾기 JAVA

커리큘럼 중 3번

프로그래머스

 

오늘은 세 번째 문제를 푸는 날이다. 

이번 문제는 이미 풀어놨던 문제라 과거에 제출했던 코드가 남아있었다.

 

과거 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] check = new boolean[n+1];
        check[0] = check[1] = false;
        
        for(int i=2; i<=n; i++) check[i] = true;
        
        for(int i=2; i<=Math.sqrt(n); i++) {
            if(!check[i]) continue;
            for(int j = i; i*j<=n; j++) check[i*j] = false;
        }
        
        for(int i=2; i<=n; i++) {
            if(check[i]) answer++;
        }
        return answer;
    }
}

 

뭘 주저리 주저리 많이도 써놨다. 쓸데없는 코드는 왜 있는지 모르겠다.

핵심 코드는 가운데 있는 이중 for문이다.

과거 코드와는 다르게 풀어볼까 생각해봤는데, 내가 에라토스테네스보다 똑똑할리 없으니 

그냥 에라토스테네스의 체를 사용하기로 했다.

대신, 배열 말고 영한쓰 자바에서 배운 삭제가 빠아른 링크드 리스트를 써볼까하다가

아무리 삭제가 빠르다해도 일차원 배열을 솎는 것보단 느릴 거 같아서 일차원 배열로 돌아왔다.

적재적소에 맞게 쓰는게 참 어려운 것 같다.

 

현재 코드

import java.util.*;

class Solution {
    public int solution(int n) {
        Boolean[] check = new Boolean[n+1];
        Arrays.fill(check, true);
        check[0] = false; check[1] = false;
        
        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(!check[i]) continue;
            for(int j = i; i * j <= n; j++) {
                check[i*j] = false;
            }
        }
        
        return Collections.frequency(Arrays.asList(check),true);
    }
}

핵심 코드는 바뀐게 없다. 그냥 안에 있는 for문 괄호 만들어주기.

일하면서 조건문이 아닌 반복문 같은 경우는 아무리 한줄짜리 코드가 있다해도 괄호를 사용하는 습관이 들었다.

그 다음으로 바뀐 건 check 배열을 boolean의 wrapper인 Boolean을 사용했다.

boolean을 사용하면 배열의 모든 원소가 boolean 기본값인 false로 채워지긴 하는데..

어차피 모든 원소를 true로 만들어주는 작업이 필요해서  List로 변경하기 쉽게 Boolean을 사용했다.

그리고 과거엔 for문을 사용해서 check 배열의 모든 원소를 true로 바꿔줬지만

이번에는 Arrays.fill()을 사용해서 더 간단하게 true로 변경했다.

그리고 [0]번과 [1]번은 사용하지 않은 인덱스라 false로 지정해줬다.

마지막 return은 Collections.frequency()를 통해서 배열 안에 두 번째 매개변수의 값이 몇개인지 구했다.

Collections.frequency()에 첫 번째 매개변수에는 Collection을 넣어야해서 List로 변환 후 넣어줬다.

 

 

오늘의 코딩 끝!

인줄 알았으나 프로그래머스 창을 닫고...... 핸드폰 하다가 갑자기 번뜩!!!!!!!!!!!!

 

코딩..그만

굳이.. 왜.... 배열 안에 true 개수를 세야하지? 라는 생각이 들어

코드를 변경했다.....

 

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = n-1; // 추가
        boolean[] check = new boolean[n+1]; // Boolean -> boolean으로 수정
        Arrays.fill(check, true);
        check[0] = false; check[1] = false;
        
        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(!check[i]) continue;
            for(int j = i; i * j <= n; j++) {
                if(check[i*j]) { // 추가
                    check[i*j] = false;
                    answer--; // 추가
                }
            }
        }
        
        return answer; // 수정
    }
}

 

 

전체적으로 시간이 매우 줄어든 것을 확인할 수 있다..!

쉽게쉽게 생각하기 다시 한 번 느낀다..