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

소수 찾기

문제 설명

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

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

제한사항

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

풀이 방법

• permutations로 순열을 구함
• 소수 판별 알고리즘 작성

from itertools import permutations
import math

def solution(numbers):
    answer = 0
    candidates = [] # numbers의 숫자들을 조합하여 만들 수 있는 모든 수를 담을 리스트
    # 1개부터 numbers의 길이까지 num개를 뽑아서 순열을 구함
    for num in range(1, len(numbers) + 1): 
        temp = list(permutations([x for x in numbers], num))
        candidates += [int(''.join(temp[i])) for i in range(len(temp))]
    candidates = set(candidates)
    
    for number in candidates:
        if is_prime_number(number): answer += 1
    
    return answer

# 소수인지 아닌지 판별하는 함수
def is_prime_number(x):
	# 0 또는 1일 경우 소수가 아님
    if x < 2:
        return False
    else:
    	# 2부터 x의 제곱근까지의 수를 나누어보아 나누어 떨어지면 소수가 아님
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        return True