Java] 프로그래머스 lv.1, 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921?language=java 

프로그래머스

 

풀이.. ㅋㅋ

 

이거 진짜 단순하게 생각하면 개에바임.. 효율성 무조건 걸림.

초기에 무식하게 계산한 로직은 아래에 있음. 이건 아니다 싶어서 수학적인 식이 있나 검색, 걸린 식으로 접근하기로 함.

 

에라토스테네스의 체 라는 것이 있는데..

에라토스테네스의 체에 대해서는 아래의 링크에 기재해두었다.

https://itstudy-mary.tistory.com/576

Java, Kotlin] 에라토스테네스의 체

 

이를 함수로 표현하면

import java.util.ArrayList;

class Solution {

    public int solution(int i) {
        
        int answer = 0;

        ArrayList<Boolean> solutionArray = new ArrayList<>();

		// true는 살아남은 값, false는 삭제된 값으로 가정한다.
		// 0과 1은 소수에서 제외한다.
        solutionArray.add(0, false);
        solutionArray.add(1, false);

		// 일단 전체를 소수로 가정한다.
        // 풀이로 치면, 1 ~ n 까지의 값을 깔아두는 것과 같다.
        for(int j = 2; j <= i; j ++) {
            solutionArray.add(j ,true);
        }

		// 앞서 말했다시피, 제곱근 값만 구하면 되기 때문에 j * j <= i; 로서 값을 줄일 수 있다.
        for(int j = 2; j * j <= i; j ++) {
        	// 만약 true라면 배수 제거 단계에서 사라지지 않았으므로, 소수로 간주하고 해당 값의 배수를 빼버린다.
        	// 해당 부분에서 4, 6 .. 뭐 이런 값들이 걸러진다.
            if(solutionArray.get(j)) {
            	// 해당 값의 배수를 빼버리는 로직이다.
                // j * j를 하는 이유는, 앞서 있는 j - 1의 값들이 전부 앞에서 미리 검사되기 때문인데,
                // ex. j가 2일때 2 + 2 + 2 + 2 + 2 를 미리 실행했기 때문에,
                //     j가 5일때 5 * 2 를 실행할 필요가 없는 것이다.
                // 다만, j * 2를 해도 효율성에서 걸리진 않는다(ㅋㅋ)
                // k += j 를 통해 j값을 꾸준히 더함으로서 배수를 구현, 배수를 전부 false로 만든다.
                for(int k = j * j; k <= i; k += j) {
                    solutionArray.set(k, false);
                }
            }
        }

		// true값을 찾아 소수값에 넣음
        for(int j = 0; j < solutionArray.size(); j ++ ) {
            if(solutionArray.get(j)) {
                answer += 1;
            }
        }

		
        return answer;
        
    }
}

 

 

++ )  처음에 짠, 시간초과 걸리는 로직.

초기에는 소수를 저장할 ArrayList를 만들었다.

2값을 넣어야 하니 2에서 출발, 리스트가 비어있으면 값을 넣는다. 즉 2는 필수적으로 들어가게 된다.

소수 테이블에 포함된 값들을 나누어 나머지가 0이라면 배수로 간주하여 중복 for문을 탈출, 모든 값을 나누어 봤음에도 나머지가 0이 아니라면 해당 값을 소수로 간주, 리스트에 넣는 방법을 고안했다.

그러나 해당 문제는 값이 1000000까지 n이 주어지므로 시간초과가 걸리는 것 같다.

500까지만 해도 소수는 95개이다.  500번의 턴을 돌며 일일히 95번의 나눗셈을 하는 것은 최대 47500번의 루프를 만들며, 이는 숫자가 커질수록 기하급수적으로 늘어날 것이기 때문에 시간초과와 효율성에서 탈락한 것 같다. 차라리 메모리를 어느정도 감안하더라도 백만개의 배열을 만든 후에 배열의 값만 변경하는 것이 더 메모리상 효율적인 듯.

    public static int solution(int n) {

        ArrayList<Integer> resultArrayList = new ArrayList<>();

        for (int i = 2; i <= n; i++) {

            if (resultArrayList.size() == 0) {
                System.out.println("?????");
                resultArrayList.add(i);
            }

            for (int j = 0; j < resultArrayList.size(); j++) {
                if (i % resultArrayList.get(j) == 0) {
                    break;
                } else if (i % resultArrayList.get(j) != 0 && j == resultArrayList.size() - 1) {
                    resultArrayList.add(i);
                    System.out.println("add ? : " + i);
                }

            }

        }

        return resultArrayList.size();
    }