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

문제 설명

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

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

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

 

문제 풀이

숫자의 자릿수는 1~numbers의 길이만큼 늘어날 수 있습니다

for문을 통해 1~numbers의 길이만큼 반복하면서 자릿수에 해당하는 숫자들을 만들고소수인지 체크하여 HashSet에 넣어주면 중복값을 제거할 수 있습니다.

 

풀이 코드

import java.util.*;
class Solution {
    private Set<Integer> numSet = new HashSet();
    public int solution(String numbers) {
        char[] numArr = numbers.toCharArray();
        for(int i=1; i<=numArr.length; i++)
            makeCase(numArr, 0, i, new int[numArr.length], new boolean[numArr.length]);
        return numSet.size();
    }
    
    private void makeCase(char[] numArr, int cnt, int size, int[] idxArr, boolean[] visit){
        if(cnt == size){
            String numStr = "";
            for(int i=0; i<size; i++) numStr += numArr[idxArr[i]];
            int num = Integer.parseInt(numStr);
            if(isPrime(num)) numSet.add(num);
            return;
        }
        
        for(int i=0; i<numArr.length; i++){
            if(!visit[i]){
                visit[i] = true; idxArr[cnt] = i;
                makeCase(numArr, cnt+1, size, idxArr, visit);
                visit[i] = false;
            }
        }
    }
    
    private boolean isPrime(int n){
        if(n < 2) return false;
        for(int i=2; i<=Math.sqrt(n); i++)
            if(n%i==0) return false;
        return true;
    }
}

 

<출처>

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

코딩테스트 연습 - 소수 찾기