알고리즘 스터디 - 5주차

알고리즘 스터디 5주차 과제로 프로그래머스 ‘소수찾기’ 문제를 풀이하였다.

해당 문제는 순열로 숫자 조합을 모두 찾고, 각 숫자가 소수인지 아닌지 판별하는 두 과정이 필요하다고 생각했다.

먼저, 완전탐색에서 재귀를 활용해 permutation함수로 문자열 numbers에서 만들 수 있는 숫자 조합을 모두 찾아 중복되는 숫자를 거르기 위해 HashSet에 숫자를 담는다.

그 후 isPrime함수를 통해 해당 숫자가 소수인지를 판별하여 소수이면, count를 증가시키고, 최종적으로 count를 answer에 저장하여 반환한다.

import java.util.*;

class Solution {
    private static HashSet<Integer> hashSet = new HashSet<>();
    private static int count = 0;
    
    public static int solution(String numbers) {
        //모든 조합의 숫자 찾기
        permutation("", numbers);
        System.out.println(hashSet);

        //소수 찾기
        for (Integer i : hashSet) {
            if(isPrime(i)) {
                count++;
            }

        }
        int answer = count;
        return answer;

    }

    public static void permutation(String comb, String others){

        if(!Objects.equals(comb, "")){
            hashSet.add(Integer.valueOf(comb));
        }

        for(int i=0; i<others.length(); i++){
            String newComb = comb+others.charAt(i);
            String newOthers = others.substring(0,i)+others.substring(i+1);

            permutation(newComb,newOthers);

        }

    }

    public static boolean isPrime(int num) {
        if(num==1||num==0){
            return false;
        }
        if(num==2){
            return true;
        }
        for (int i = 2; i < num - 1; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        System.out.println("prime:"+num);
        return true;

    }

}