[Programmers Lv.2][소수 찾기][java]

문제 링크

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

프로그래머스

---

제한 사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

알고리즘

1. 있는 종이 카드로 조합 가능한 수들을 만들어 hashset에 넣는다. (중복 방지) → 재귀
2. hashset 에 있는 수들을 소수 판별하여 카운트해준다.

cntPrime(hs.toArray(new Integer[0]))
Integer[]::new
new Integer[0]
new Integer[]{}
-> 모두 같은 것

A = a*b 라고 가정했을 경우, a와 b 모두 제곱근A보다 클 수 없다.
따라서 a와 b의 곱으로 이루어진 A는 제곱근 A까지만 확인해도 소수인지 확인할 수 있다.

ex. "1" , "23" : 1 추가하고 반복 → ("12", "3"), ("13", "2")
("12", "3") : 12 추가하고 반복 → (”123”, “”)
("13", "2") : 13 추가하고 반복 → (”132”, “”)

 

전체 코드

import java.util.*;

class Solution {
    HashSet<Integer> hs = new HashSet<>();
    public int solution(String numbers) {
        numCombinations("", numbers);
        return cntPrime(hs.toArray(new Integer[0]));
    }

    public void numCombinations(String str, String tmp) {
        if (!str.equals("")) hs.add(Integer.parseInt(str));
        for (int i = 0; i < tmp.length(); i++) {
            numCombinations(str + tmp.substring(i, i + 1),
                    tmp.substring(0, i) + tmp.substring(i + 1));
        }
    }

    public int cntPrime(Integer[] arr){
        int cnt = 0;
        for (int i = 0; i < arr.length; i++) {
            if (isPrime(arr[i]))
                cnt++;
        }
        return cnt;
    }

    public boolean isPrime(int num) {
        if (num <= 1) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}