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

 

대회명/문제출처: 프로그래머스

난이도: ★★★☆☆

• 문제 분류: 완전 탐색

[문제]

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

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

 

---

[분석]

순열과 에라토스테네스의 체 문제가 결합된 문제이다.

itertools라는 내장함수를 통해 순열값을 튜플로 구하고 정수형태로 변환하는 방법을 택했다. 

 

---

[코드]

from itertools import *

def isprime(num):
	prime_list=[]
	n=[True for _ in range(num+1)]
	for i in range(2,num+1):
		if n[i]:
			prime_list.append(i)
			for j in range(i*2,num+1,i): 
				n[j]=False

	return prime_list
        

def solution(numbers):
    answer = 0
    lst=[]
    for i in range(1,len(numbers)+1):
    	lst.append(list(permutations(numbers,i)))
    list2 = list(chain(*lst))
    numb=[]
    for i in range(0,len(list2)): 
    	numb.append(int("".join(list(list2[i]))))
    tu_numb=list(set(numb))
    prime_list=isprime(max(tu_numb))
    for i in range(0,len(tu_numb)):
    	if tu_numb[i] in prime_list: 
    		answer+=1
    return answer