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

소수 찾기 문제 풀이

 

💻Q

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.
흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때,
종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

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

입출력 예

예제

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

#2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.

 

💡A

이 문제는 소수와 순열 알고리즘 공부가 필요했다. 
소수(prime number)란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.
1은 합성수도 소수도 아니다.
어떤 수 n이 a x b 일때, a와 b 중 하나는 n의 제곱근보다 작거나 같기 때문에 n의 제곱근까지만 나누었을때 나누어떨어지는 약수가 없다면 소수라고 할 수 있다. 

String으로 받은 numbers를 split() 메소드로 나누어주고 연산이 가능해지도록 Integer.parseInt() 메소드로 int형으로 변환해 준 뒤 int형 배열에 저장한다.
swap 방식의 perm() 메소드로 순열을 구하고 StringBuilder로 값을 변경해 배열로 저장한다.
제곱근을 이용해 소수를 찾는 makePrime() 메소드로 소수를 구한 뒤 중복값이 없어야 할때 쓰이는 자료구조인 Set에 저장하여 길이를 리턴해 답을 구한다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        String[] strArr = numbers.split("");
        int[] intArr = new int[strArr.length];

        for(int i = 0; i < intArr.length; i++) {
            intArr[i] = Integer.parseInt(strArr[i]);
        }

        Set<Integer> set = new HashSet<>();

        for(int i = 1; i <= intArr.length; i++) {
            perm(strArr, 0, i, set);
        }
        answer = set.size();
        return answer;
    }

    public void makePrime(Set set, StringBuilder sb) {
        int num = Integer.parseInt(String.valueOf(sb));
        boolean prime = true;

        if(num <= 1) {
            return;
        }

        for(int i = 2; i <= Math.sqrt(num); i++) {
            if(num % i == 0) {
                prime = false;
                break;
            }
        }

        if(prime) {
            set.add(num);
        }
    }

    public void perm(String[] arr, int depth, int k, Set set) {
        if(depth == k) {
            permArr(arr, k, set);
            return;
        }
        else{
            for(int i = depth; i < arr.length; i++) {
                swap(arr, i, depth);
                perm(arr, depth+1, k, set);
                swap(arr, i, depth);
            }
        }
    }
    public void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void permArr(String[] arr, int k, Set set) {
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < k; i++) {
            sb.append(arr[i]);
        }
        makePrime(set, sb);
    }
}​

 

---

👀 참고

순열 알고리즘
소수 알고리즘

순열(Permutation) 알고리즘

[백준] 1978번 : 소수 찾기 - JAVA [자바]