[JAVA | 프로그래머스] 소수 찾기

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

프로그래머스

 

문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제출 답안

 

개선 답안

import java.io.IOException;
import java.util.HashSet;
import java.util.Iterator;

class Solution {
    static HashSet<Integer> numberSet = 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. 에라토스테네스의 체에 따라 limit까지마나 배수의 여부를 확인한다.
        for(int i=2; i<=lim; i++){
            if(num%i==0)        // num이 i의 배수라면
                return false;
        }

        return true;
    }

    public void recursive(String comb, String others){   // comb: 현재까지 조합된 숫자, others: 현재까지 조합되지 않은 숫자
        // 1. 현재 조합을 set에 추가
        if(!comb.equals(""))
            numberSet.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) {
        int cnt = 0;

        // 1. 모든 조합의 숫자를 만듦
        recursive("", numbers);
        
        // 2. 소수의 개수 세기
        Iterator<Integer> it = numberSet.iterator();    
        while(it.hasNext()){    // numberSet의 모든 원소를 다 돈다 (==for문)
            int number = it.next();
            if(isPrime(number))
                cnt++;
        }

        // 3. 소수 개수 반환
        return cnt;
    }
}

 

 

참고 자료

https://www.youtube.com/watch?v=pF368QqdQb4