소수 찾기

문제 설명

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

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

제한사항

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

입출력 예numbersreturn

"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

- 문제 분석

numbers는 한자리 숫자들이 섞인 문제열임

이 숫자들을 조합해 만들 수 있는 모든 수 중 소수가 몇개인지를 구해야함

중복 없이 소수를 세야함

종이 조각을 붙이는 것이기 때문에 순서를 바꿔 숫자를 만들 수 있음

숫자의 자릿수를 1자리부터 n자리까지 모두 고려해야함

 

- 접근 방법

필요 알고리즘 요소

모든 조합 생성: 문자열로 주어진 숫자들의 모든 순열을 만들어야함

길이 1부터 n까지의 모든 순열을 고려해야함

 

중복 제거: set을 사용해 중복된 숫자 제거

011과 11처럼 앞에 0이 붙은 경우 정수로 변환해서 011 -> 11로 처리해주어야함

 

소수 판별: 만들어진 각 숫자가 소수인지 판별

에라토스테네스의 채를 사용할 수도있고, 각각을 검사해도 괜찮음

 

numbers의 각 자리로 만들 수 있는 모든 순열 생성(길이 1~n) -> 각 순열을 숫자로 변환 후 set에 저장(중복 제거)

-> 저장된 숫자 중 소수인지 판별하여 개수 카운트 -> 최종 카운트 리턴

 

구현 과정

우선 중복을 방지하기 위해 Set으로 설정을 해줌

static Set<Integer> primeSet = new HashSet<>();

 

다음으로 배열을 통해 중복을 방지해주기위해 방문 배열을 선언해주었습니다.

boolean[] visited = new boolean[numbers.length()];

 

백트래킹을 통해 구현을 해주었습니다

현재 cur이라는 문자구성이 0보다 크다면 해당 문자를 숫자로 변환해주고 소수판별을 진행해준후 소수가 맞다면 set에 넣어주었습니다.

그 후 numbers의 크기만큼 재귀적으로 백트래킹 함수를 호출해주며 다음 호출시엔 기존 cur에 i를 추가해주며 호출해주었습니다.

 

public static void backtrack(String numbers, boolean[] visited, String cur) {
        if (cur.length() != 0) {
            int num = Integer.parseInt(cur);
            if(isPrime(num)) {
                primeSet.add(num);
            }
        }
        
        for(int i = 0; i < numbers.length(); i++) {
            if(!visited[i]) {
                visited[i] = true;
                backtrack(numbers, visited, cur + numbers.charAt(i));
                visited[i] = false;
            }
        }
    }
    
    public static boolean isPrime(int num) {
        // 0과 1은 소수아님
        if(num < 2) {
            return false;
        }
        for (int i = 2; i*i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

 

최종 코드

import java.util.*;
class Solution {
    static Set<Integer> primeSet = new HashSet<>();
    public int solution(String numbers) {
        boolean[] visited = new boolean[numbers.length()];
        backtrack(numbers, visited, "");
        return primeSet.size();
    }
    
    public static void backtrack(String numbers, boolean[] visited, String cur) {
        if (cur.length() != 0) {
            int num = Integer.parseInt(cur);
            if(isPrime(num)) {
                primeSet.add(num);
            }
        }
        
        for(int i = 0; i < numbers.length(); i++) {
            if(!visited[i]) {
                visited[i] = true;
                backtrack(numbers, visited, cur + numbers.charAt(i));
                visited[i] = false;
            }
        }
    }
    
    public static boolean isPrime(int num) {
        // 0과 1은 소수아님
        if(num < 2) {
            return false;
        }
        for (int i = 2; i*i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}