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

문제 설명

숫자가 적힌 종이 조각이 흩어져있을 때, 종이 조각들로 만들 수 있는 소수가 몇 개 인지 구하는 문제

 

• 알고리즘 분류 - Brute Force (완전 탐색)
• 난이도 - Level 2

---

접근 방법 - Brute Force

주어진 문자열에 대해 원소의 개수가 i개인 순열을 모두 구하고, 순열을 문자열로, 문자열을 정수로 변환하여 소수인지 판별

---

답안 코드 - Brute Force

from itertools import permutations

def is_prime(num):
    if num < 2:
        return False
    if num == 2:
        return True
    for i in range(2, num):
        if num % i == 0:
            return False
        if i == num-1:
            break
    return True

def solution(numbers):
    answer = 0
    
    primes = []
    for i in range(1, len(numbers)+1):
        perms = list(permutations(numbers,i))
        
        for perm in perms:
            s = int(''.join(perm))
            if is_prime(s) == True:
                primes.append(s)
                        
    answer = len(set(primes))
    return answer