[완전탐색 / 프로그래머스] 42839번 : 소수찾기

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

 

Lv2 문제이고, 스스로 푼 문제다!

주어진 numbers 숫자를 구성하는 숫자들로 만들수 있는 소수의 갯수를 찾는 문제다.

여기서 4자리 수라면 1자리 수부터 4자리수까지 나열할 수 있는 경우는 모두 다 나열한 다음, 그 중에서 소수를 중복되지 않게 세는 것이 중요하다

그래서 나열하는 경우는 permutations로 구현했고, 중복되지 않게 세는 것은 check 배열을 이용해서, 여기에 없는 수만 세도록 했다

 

 

- 정답 풀이 :

import math
from itertools import permutations

def isPrime(num):
    flag = True
    if num == 1 or num == 0:
        return False
    
    for i in range(2, int(math.sqrt(num) + 1)):
        if num % i == 0:
            return False
        
    if flag:
        return True
              
def solution(numbers):
    
    numbers = list(numbers)
    n = len(numbers)
    
    answer = 0
    check = []
    for i in range(1, n + 1):
        #순열로 i자리수 숫자를 임의 생성한다
        result = permutations(numbers, i)
        #만들어진 i자리수 수 중에서 소수이고, 중복이 안되는 경우를 센다 
        for x in result:
            temp = int(''.join(x))           
            if isPrime(temp) and temp not in check:
                answer += 1
                check.append(temp)
        
    return answer