[프로그래머스/ 고득점 kit] 완전탐색: 소수찾기

 

permutation+ 중간 과정에서 발생하는 조각들 더하기 + 중복 제거(set) + 소수 찾기 알고리즘

 

 

 

1. 문제링크

https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기 | 프로그래머스

 

 

 

 

 

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