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

문제를 해결하기 위해서는 크게 두 부분이 필요했다.

첫 번째는 주어진 numbers에서 모든 조합을 찾는 것이고

두 번째는 조합에서 소수를 판별해서 그 개수를 반환하는 것이다.

 

소수를 판별하는 부분은 금방 작성했지만 모든 조합을 찾는데 시간이 정말 오래 걸렸다.

모든 조합을 찾는 방법이 재귀, 백트래킹 등등 어려 방법이 있었는데 

재귀를 거의 써본 적이 없어서 재귀 기본 강의를 듣고

실제 코드 작성은 막히는 부분마다 검색으로 해결하여 풀었다.

프로그래머스 말고도 백준에서 재귀와 백트래킹 유형을 풀면서 익숙해져야겠다.

---

최종 코드

import java.util.HashSet;
import java.util.Iterator;
class Solution {
    // 전역변수로 HashSet 선언
    HashSet<Integer> hs = new HashSet<>();

    public int solution(String numbers) {
        // 재귀를 이용해서 모든 조합 만들기
        rec("", numbers);

        // 소수 개수 세기
        int cnt = 0;
        // Iterator를 이용하여 해시셋 탐색
        Iterator<Integer> ite = hs.iterator();
        while (ite.hasNext()) {
            int number = ite.next();
            // 소수이면 cnt 증가
            if(primeNumber(number)) {
                cnt++;
            }
        }
        return cnt;
    }

    // 재귀를 이용한 조합 메소드
    public void rec (String temp, String n) {
        // 현재 조합을 set에 추가
        if(!temp.equals("")) {
            hs.add(Integer.parseInt(temp));
        }

        // 나머지 숫자를 더해 조합 만들기
        for (int i = 0; i < n.length(); i++) {
            // 재귀 호출
            rec(temp + n.charAt(i), n.substring(0, i) + n.substring(i + 1));
        }
    }

    // 소수 판별 메소드
    static boolean primeNumber(int n) {
        if(n == 0 || n == 1) return false;
        for (int i = 2; i < n; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }

}