permutation+ 중간 과정에서 발생하는 조각들 더하기 + 중복 제거(set) + 소수 찾기 알고리즘
1. 문제링크
https://programmers.co.kr/learn/courses/30/lessons/42839
코딩테스트 연습 - 소수 찾기 | 프로그래머스
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이
programmers.co.kr
2. code:
import math
def solution(numbers):
# make list having all case numbers
list_numbers = P(numbers)
# delete overlap
set_numbers = {int(x) for x in list_numbers}
# count saving variable
answer = 0
# all variable in set
for item in set_numbers:
# check
check_prime_res = check_prime(item)
# if item is prime, increase count
if check_prime_res :
answer+=1
else:
pass
return answer
# prime check function
def check_prime(num):
if num == 0 or num == 1:
return False
if num == 2 :
return True
# 16 is checked 2~4
# 25 is checked 2~5
# n is checked 2~sqrt(n)
sqrt_num = int(math.sqrt(num))
for i in range(2,sqrt_num+1):
if num%i == 0:
return False
return True
# permutation code and frags append
# "17" makes ['1','7','17','71']
# "011" makes
#['011', '11', '01', '1', '011', '11', '01', '1',
# '101', '01', '11', '1', '110', '10', '10', '0',
#'101', '01', '11', '1', '110', '10', '10', '0']
def P(lst):
res = []
size = len(lst)
if size == 1:
return lst
else:
for i in range(size):
rem = lst[:i]+ lst[i+1:]
p_res = P(rem)
for r in p_res:
# for full number permutaion append
res.append(lst[i]+r)
# for frags append in process working
res.append(r)
return res