[프로그래밍 문제] 소수 찾기

문제 설명

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

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

제한사항

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

입출력 예

numbers return
"17" 3
"011" 2

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

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

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

생각한 방법

1. 조합 가능한 모든 수를 만든다.
2. 소수이면 Set에 추가한다

이렇게 생각한 이유

numbers의 길이가 최대 7까지이므로 조합가능한 수가 크지 않으므로 완전 탐색으로 진행한다.
중복되는 수가 나올 수 있으므로 Set을 이용해 중복되는 값은 카운트하지 않는다.

import static java.lang.Math.sqrt;
import java.util.stream.*;
import java.util.*;
class Solution {
    Set<Integer> hashSet = new HashSet<>();
    
    public int solution(final String numbers) {
        recursive("", numbers);
        return hashSet.size();
    }
    
    public void recursive(final String a, final String b){
        final int n = a.isEmpty() ? 0 : Integer.valueOf(a);
        if(isPrime(n)) hashSet.add(n);
        for(int i=0;i < b.length();i++)
            recursive(a+b.charAt(i), b.substring(0, i) + b.substring(i+1));
    }
    
    public boolean isPrime(final int num) {
        return num > 1 && IntStream.rangeClosed(2, (int)sqrt(num)).noneMatch(n -> (num % n == 0));
    }
    
}

결과

정확성  테스트
테스트 1 〉	통과 (11.69ms, 75MB)
테스트 2 〉	통과 (20.55ms, 74.6MB)
테스트 3 〉	통과 (10.87ms, 73MB)
테스트 4 〉	통과 (19.28ms, 75.7MB)
테스트 5 〉	통과 (34.34ms, 93.1MB)
테스트 6 〉	통과 (14.82ms, 89MB)
테스트 7 〉	통과 (13.26ms, 79.2MB)
테스트 8 〉	통과 (31.81ms, 100MB)
테스트 9 〉	통과 (11.57ms, 90.5MB)
테스트 10 〉	통과 (22.90ms, 83.3MB)
테스트 11 〉	통과 (18.51ms, 78.1MB)
테스트 12 〉	통과 (17.91ms, 85.6MB)

풀이 설명

재귀 함수를 이용해 모든 경우의 수를 탐색하고, 에라토스테네스의 체를 이용해 소수를 확인했다. 소수를 확인하면 Set에 추가하고 Set의 사이즈를 반환한다.

recursive 함수를 보면 a, b 매개 변수가 있는데 a가 경우의 수라고 보면되고, 경우의 수를 만들고 남은 수가 b에 있다고 보면된다.

int n에 문자열 타입인 a를 int형으로 캐스팅한다. 만약 ""이면 0으로 치환한다.
n이 소수면 Set에 추가한다. 소수 확인은 isPrime() 함수를 통해 한다.

isPrime() 함수는 num을 매개변수로 받아 2에서부터 num의 제곱근까지 num을 나눈 나머지가 0이 아니면 true(소수)를 반환한다.

recursive로 돌아가서 모든 경우의 수를 탐색하기 위햇 recursive함수를 호출한다. a 매개변수에는 기존 a + b의 값중 1개, b값에는 a 매개 변수에 준 값을 제외한 나머지를 준다.
예를 들어 ("", "011")이라고 하면 for문에서 호출하는 recursive는 아래와 같다.
recursive("0", "11")
recursive("1", "01")
recursive("1", "01")
...
recursive("011", "")
이런 식으로 모든 경우의 수를 탐색할 수 있다.

재귀함수가 끝나면 Set에는 지금까지 탐색한 소수들이 들어있으므로 소수의 개수는 size()를 통해 알 수 있다.