프로그래머스 [Python] - 소수 찾기

문제

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

프로그래머스

풀이

1. itertools.permutations

def solution(numbers):
    answer = set()
    numbers = list(numbers)
    def is_prime(num):
        if num<2:
            return False
        for i in range(2,int(num**0.5)+1):
            if num%i==0:
                return False
        return True
    
	# 1. permutations
    from itertools import permutations
    for i in range(1,len(numbers)+1):
        s = set(list(map(lambda x:int(''.join(x)), permutations(numbers,i))))
        for num in s:
            if is_prime(num):
                answer.add(num)
                
	return len(answer)

2. 재귀 함수

def solution(numbers):
    answer = set()
    numbers = list(numbers)
    def is_prime(num):
        if num<2:
            return False
        for i in range(2,int(num**0.5)+1):
            if num%i==0:
                return False
        return True
                
    # 2. 재귀
    def permutation(numbers,k,res=''):
        if len(res)==k:
            if is_prime(int(res)):
                answer.add(int(res))
                return
        for _ in range(len(numbers)):
            num = numbers.pop(0)
            permutation(numbers,k,res+num)
            numbers.append(num)
    
    for i in range(1,len(numbers)+1):
        permutation(numbers,i)
        
    return len(answer)

3. 재귀 X(BFS)

def solution(numbers):
    answer = set()
    numbers = list(numbers)
    def is_prime(num):
        if num<2:
            return False
        for i in range(2,int(num**0.5)+1):
            if num%i==0:
                return False
        return True
        
    # 3. 재귀 X
    from collections import deque
    def permutation2(k,res=''):
        q = deque()
        q.append((numbers,res))
        while q:
            new_numbers,res = q.popleft()
            if len(res)==k:
                if is_prime(int(res)):
                    answer.add(int(res))
                continue
            for i in range(len(new_numbers)):
                q.append((new_numbers[:i]+new_numbers[i+1:],res+new_numbers[i]))
                
    for i in range(1,len(numbers)+1):
        permutation2(i)        
                            
    return len(answer)

 

DFS, BFS, 재귀 함수등을 활용한 combination, permutation에 대해 연습하자