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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

풀이

문자들의 조합을 구해 정수형으로 변환 후 소수인지 아닌지를 판별한다.

 

코드

자바

import java.util.*;

class Solution {
    int[] check;
    Stack<String> stack = new Stack<>();
    ArrayList<String[]> results = new ArrayList<>();
    
    public boolean isPrimeNumber(int n) {
        if (n < 2)
            return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
    
    public void DFS(String[] n, int L, int x) {
        if (x == L) {
            String[] s = new String[stack.size()];
            for (int i = 0; i < stack.size(); i++) {
                s[i] = stack.get(i);
            }
            results.add(s);
            return;
        } else {
            for (int i = 0; i < n.length; i++) {
                if (check[i] == 0) {
                    check[i] = 1;
                    stack.push(n[i]);
                    DFS(n, L, x + 1);
                    check[i] = 0;
                    stack.pop();
                }
            }
        }
    }
    
    public int solution(String numbers) {
        int count = 0;
        String[] tmp = numbers.split("");
        check = new int[tmp.length];
        
        for (int i = 1; i <= tmp.length; i++) {
            DFS(tmp, i, 0);
        }
        
        ArrayList<Integer> nums = new ArrayList<>();
        for (String[] result : results) {
            nums.add(Integer.valueOf(String.join("", result)));
        }
        
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        
        for (int i : set) {
            if (isPrimeNumber(Integer.valueOf(i))) {
                count++;
            }
        }
        
        return count;
    }
}

파이썬

from itertools import permutations
import math

def isPrimeNumber(x):
    if x < 2:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

def solution(numbers):
    count = 0
    nums = []
    for i in range(1, len(numbers) + 1):
        nums += list(map(int, [''.join(n) for n in permutations(numbers, i)]))
    nums = list(set(nums))
    
    for num in nums:
        if isPrimeNumber(num):
            count += 1
    
    return count