[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 소수찾기

📚 문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.

• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

🎯  어떻게 풀었나

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        char[] digits = numbers.toCharArray();
        HashSet<Integer> possibleNums = new HashSet<>();
        
        for(int r = 1; r <= digits.length; r++) {
            permutate(possibleNums, digits, 0, digits.length, r);
        }
        
        for(int possibleNum : possibleNums) {
            if(isPrime(possibleNum)) answer++;
        }
    
        
        return answer;
    }
    
    public boolean isPrime(int num) {
        if(num == 1) return false;
        if(num == 2) return true;
        if(num % 2 == 0) return false;
        
        int rootNum = (int)Math.sqrt((double)num);
        for(int i = 3; i <= rootNum; i+= 2) {
            if(num % i == 0) return false;
        }
        
        return true;
    }
    
    public void permutate(HashSet<Integer> comb, char[] arr, int depth, int n, int r) {
        if (depth == r) {
            StringBuilder sbd = new StringBuilder();
            for(int i = 0; i < r; i++) sbd.append(arr[i]);
            
            comb.add(Integer.parseInt(sbd.toString()));
            return;
        }
        
        for(int i = depth; i < n; i++) {
            swap(arr, depth, i);
            permutate(comb, arr, depth + 1, n, r);
            swap(arr, depth, i);
        }
    }
    
    public void swap(char[] arr, int depth, int i) {
        char temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }
}

 

🧐 왜 저렇게 풀었나

알고리즘은 간단하다.

먼저 매개변수로 주어지는 문자열 numbers의 길이가 n이라면 char형 배열로 만든다.

그리고 n개의 문자에서 1개부터 n개까지 고르는 순열들을 만들고 순열의 결과들을 HashSet에 저장해서 중복이 없도록 한다.

 

그 다음 HashSet에 저장된 숫자들이 소수인지 판별하고 소수이면 answer을 1 증가한다.

 

📖 무엇을 배웠나

permutate하는 함수는 저번에 카카오 '수식 최대화' 문제를 풀었을 때 사용한 코드를 참고해서 작성했다.

 

그리고 소수인지를 판별하는 알고리즘은 아래 블로그를 참고해서 작성했다.

https://boycoding.tistory.com/225

[프로그래머스] 소수의 합, 소수 판별 알고리즘