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

프로그래머스의 Lv.2 소수찾기 문제 풀이

문제 설명

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

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

제한 사항

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

문제 풀이
일단 모든 숫자의 조합을 만들어야했고, 소수인지 확인하는 과정도 필요한 문제였다. 여기서 모든 숫자 조합을 만든 newNumbers메서드에서는 재귀함수를 사용하여 현재만들어진 조합과 아직 사용하지 않는 숫자, 조합을 저장할 hashSet을 사용하였다. 아직 사용하지 않은 숫자를 이용하여 반복하여 숫자조합을 만드는 메서드이고, isPrime메서드는 소수인지 판단하는 메서드로 소수를 판별하는 조건문들로 해결할 수 있었다. 또한 숫자 조합들 중에 중복이 있을 수 있어 HashSet에 저장하여 최종 소수 판별 후 소수가 맞다면 카운트를 증가시켜 소수의 갯수를 반환하도록 하였다.

코드

public int solution(String numbers) {
   // 중복 제거를 위해 hashset에 저장
   HashSet<Integer> set = new HashSet<>();
   newNumbers("", numbers, set);

   int count = 0;
   for (int n : set) {
     if (isPrime(n)) {
       count++;
     }
   }
   return count;
 }

 // 모든 숫자 조합 만들기
 private static void newNumbers(String current, String remaining, HashSet<Integer> set) {
   if (!current.isEmpty()) {
     set.add(Integer.valueOf(current));
   }
   for (int i = 0; i < remaining.length(); i++) {
     newNumbers(current + remaining.charAt(i), remaining.substring(0, i) + remaining.substring(i + 1), set);
   }
 }
 // 소수인지 확인
 private static boolean isPrime(int n) {
   if (n <= 1) {
     return false;
   }
   if (n == 2) {
     return true;
   }
   if (n % 2 == 0) {
     return false;
   }
   for (int i = 3; i <= Math.sqrt(n); i += 2) {
     if (n % i == 0) {
       return false;
     }
   }
   return true;
 }