99클럽 코테 스터디 10일차 TIL 소수 찾기

 

 

 

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

프로그래머스

 

1. 문제 및 접근

 

String으로 문자열 받고 그 String으로 만들 수 있는 숫자를 구한다음 에라스토테네스의 체로 거르면

그럼 String으로 숫자들의 조합을 만들어야 하는데 중복 숫자는 못 담으니까 set으로 구성하자

 

1. 만들 수 있는 수를 다 만들기 ( set으로 재귀 및  dfs로)

 

2. 에라스토테네스의 체로 소수판별 해서 갯수 세기 (dp로 구현해야겠다.)

 

 

제한 사항

 

numbers는 길이 1 이상 7 이하인 문자열입니다.

(다 들어와도 7자리 라는 뜻이네)

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

 

 

 

 

 

 

2. 풀이법

 

public class 소수정답 {

    HashSet<Integer> numbersSet = new HashSet<>();

    public boolean isPrime(int num) {
        // 1. 0과 1은 소수가 아니다
        if (num == 0 || num == 1)
            return false;

        // 2. 에라토스테네스의 체의 limit 숫자를 계산한다.
        int lim = (int)Math.sqrt(num);

        // 3. 에라토스테네스의 체에 따라 lim까지 배수 여부를 확인한다.
        for (int i = 2; i <= lim; i++)
            if (num % i == 0)
                return false;

        return true;
    }

    public void recursive(String comb, String others) {
        // 1. 현재 조합을 set에 추가한다.
        if (!comb.equals(""))
            numbersSet.add(Integer.valueOf(comb));

        // 2. 남은 숫자 중 한 개를 더해 새로운 조합을 만든다.
        for (int i = 0; i < others.length(); i++)
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i + 1));

    }

    public int solution(String numbers) {
        // 1. 모든 조합의 숫자를 만든다.
        recursive("", numbers);

        // 2. 소수의 개수만 센다.
        int count = 0;
        Iterator<Integer> it = numbersSet.iterator();
        while (it.hasNext()) {
            int number = it.next();
            if (isPrime(number))
                count++;
        }

        // 3. 소수의 개수를 반환한다.
        return count;
    }

    public static void main(String[] args) {
        소수정답 sol = new 소수정답();
        System.out.println(sol.solution("17"));
    }

}

 

 

 

2-1. 숫자 조합 만들기

 

우리는 들어온 수를 가지고 중복되지 않은 수 전체를 만든다

 

ex) 1, 7

 

[1, 7, 17 ,71]

 

 

 

 

recursive에 빈 문자열과 남은 number를 넣어서 재귀 함수를 호출

 

 

 

 

 

1. 먼저 호출 때 마다 어떤 행동을 할 것인가 ?

 

 

 

 

먼저 처음에 들어온 수인 빈 문자열의 경우는 추가하지 않기 위해

 

combi가 " "가 아닐 경우에만 Set에 Integer로 변환 후 추가!

 

(재귀를 계속 호출할텐데 그때마다 만들어진 combi가 set에 계속 추가됨)

 

 

 

 

 

2. 어떻게 조합을 만들 것인가 ?

 

 

 

남아있는 other(현재 쓰고 남은 숫자)까지 돈다.

 

다음 재귀를 호출하는데, comb인 현재 만들어진 숫자는 = others의 남은 수 i번째

 

comb =   " "

others = "17"

 

이라면 (i)인 1을 comb으로 넘겨주고, 남은 others는 i를 사용했으니 i를 빼고 넘겨주고 싶을 것이다.

 

그렇다면 substring으로 0번째 index부터, i까지  +  i+1의 인덱스를 가진 애부터 끝까지 (둘이 다른 메서드)

 

 

 

주의 !

substring가 시작 인덱스와 끝 인덱스가 주어지면 끝 인덱스는 포함안됨 (전까지)

 

 

 

 

즉 

재귀 호출 과정은

 

 

1.   comb = " "    ,   others = "17"     set = {null}

 

2.  comb = "1"   ,   others = "  7"     set = {1}

 

3.  comb = "17" ,   ohters = "    "     set = {1, 17}

 

4.  others가 없기에 다시 빠져나와 원래 호출한 부분으로 감

 

5.  comb = "17"  중복이기에 제외                                    (2-1의 과정)   

 

6. comb = "7"   ,   others = " 1"        set = {1, 17 , 7}  (1-1의 과정)

 

7. ~~

 

 

 

끝엔 결국 중복을 제외한 set에 {1, 17, 7, 71} 이 저장된다   

*순서는 그냥 보기 쉽게 표기해봄

 

 

 

 

 

 

2-2. 소수 판별

 

 

 

 

 

numberSet으로 만들어진 set을 iterator로 돌면서 확인

 

it.next의 수를 소수 판별 메서드 isPrime()으로 넘겨주고,

 

맞다면 count++;

 

 

 

 

1. 에라토스테네스의 체 (isPrime)

 

 

기저 조건으로는 0과 1은 소수가 아니니 들어오면 바로 false

 

 

소수를 판별하는 유명한 방법으로 "에라토스테네스의 체" 가 있다.

 

 

 

n의 소수인지 파악하기 위해

n-1까지의 모든 배수를 확인하는 것이 아닌, 그 수의 제곱근까지 판별해서 빠르게 소수의 여부를 확인

 

 

 

i는 2부터 들어온 소수의 제곱근까지 배수인 지 아닌 지 판별하고,  배수라면 소수가 아닐 것이다.

 

 

71이라면 8.~~까지   확인한단 뜻!

 

 

 

{1, 7 ,17 ,71} 중

 

 

7, 17, 71이 소수임으로 3개 !

 

 

 

 

 

 

 

3.  마무리

 

 

 

dfs로 판별 여부를 정해서 풀어보려다가 실패했다..

 

소수는 찾기 쉬워서 들어온 String으로 전체 수를 만드는데

애를 먹어서 다른 사람의 풀이를 조금 참고 했는데 참고하니 너무 쉽게만 느껴져서 조금만 더 참아볼껄 ㅠㅠ

 

핵심은 재귀를 호출하는 점인데, 어렵다면 차근차근 하나씩 그려보며 호출과정을 읽는 것을 추천한다..

(아직도 나도 직관적으로 되지가 않음)

 

다음에는  dp로 시간 복잡도도 줄여보자..