[level 2] 소수 찾기 - 42839 (JAVA)

문제 요약

 

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

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

---

문제 분석

 

가능한 경우를 모두 구해 Set에 넣어 중복을 제거하며 정말탐색한다.

---

코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        // 문자열 numbers를 int 배열로 변환
        int[] numArr = numbers.chars().map(n -> n - '0').toArray();
        // 소수를 저장할 Set를 생성
        Set<Integer> primes = new HashSet<>();
        // 재귀적으로 소수 찾기
        getPrimes(0, numArr, primes, new boolean[numArr.length]);
        // Set의 크기가 정답
        answer = primes.size();
        return answer;
    }
    
    private boolean isPrime(int num){
        // 1 이하는 소수가 아님
        if(num <= 1){
            return false;
        }
        // 2부터 주어진 수의 제곱근까지의 모든 수로 주어진 수를 나누기
        for(int n = 2; n <= Math.sqrt(num); n++){
            // 만약 주어진 수를 나눌 수 있으면 소수 아님
            if(num % n == 0)
                return false;
        }
        // 주어진 수를 나누는 수가 없으니 이건 소수임
        return true;
    }
    
    private void getPrimes(int currNum, int[] numArr, Set<Integer> primes, boolean[] visited){
        // 현재 숫자가 소수인지 판별하고, 소수라면 Set에 추가
        if(isPrime(currNum))
            primes.add(currNum);
        // 배열에 들어있는 모든 수 탐색
        for(int i = 0; i < numArr.length; i++){
            // 이미 사용된 숫자는 건너뛴다
            if(visited[i] == true)
                continue;
            // 이거 이제 사용함
            visited[i] = true;
            // 다음 숫자는 현재 숫자에 10을 곱하고 새로운 수 더한 값임
            int nextNum = currNum * 10 + numArr[i];            
            // 다음 숫자로 재귀 집어넣기
            getPrimes(nextNum, numArr, primes, visited);
            // 방문배열 되돌리기
            visited[i] = false;
        }
    }
}

---

정리

새로 배운 내용

없음

개선할 점

뭔가 이렇게까지 길어질 코드가 아닌 거 같은데 나중에 확인 한번 해봐야 할 듯하다.

더 찾아볼만한 사항

stream을 좀 더 사용해 볼 수 없을까?

---