소수 찾기

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

---

풀이

import java.util.*;

class Solution {
    Set<Integer> set = new HashSet<>();

    public int solution(String numbers) {
        repeat("", numbers);
        return set.size();
    }

    public void repeat(String s, String numbers) {
        for(int i = 0; i < numbers.length(); i++) {
            String s2 = s + numbers.charAt(i);
            int n = Integer.parseInt(s2);
            int m = n / 2;
            boolean flag = n >= 2 && !set.contains(n);
            if(flag)
                for(int j = 2; j <= m; j++)
                    if(n % j ==0) {
                        flag = false;
                        break;
                    }
            if(flag) set.add(Integer.parseInt(s2));
            repeat(s2, numbers.substring(0, i) + numbers.substring(i + 1));
        }
    }
}

1. 매개변수 numbers를 repeat 함수로 ""와 함께 넘겨준다.

    2. 입력받은 numbers문자열의 길이만큼 반복문을 실행한다.

        3. 이전에 넘어온 문자열 s와 numbers의 각 문자를 합친다.(variable: s2)

        4. 합친 문자열을 int로 바꿔준다.

        5. 합친 문자열이 소수인지, 정답목록에 들어있는 숫자인지 확인한다.

        6. 소수이고, 정답목록에 없다면 정답목록에 추가해준다.

        7. 3번에서 합친 문자열 s2와 내가 더한 문자인 s를 numbers에서 제외하고, repeat함수를 다시 호출한다.

8. repeat함수가 모두 실행되고 나면 정답 목록의 개수를 반환해준다.

 

소수를 검사하는 로직에 대해 자세하게 설명하진 않았다! 통상적인 방법이고, 검색해보면 금방 찾을 수 있을 것이다!