[Python3]프로그래머스_소수 찾기

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42839/solution_groups?language=python3

접근법

문제에서 모든 접근법을 다 알려줬다.
이는 얼마나 효율적으로 빠르게 짜느냐가 관건인 것 같다.
가능한 모든 조합의 숫자들을 구하고 소수인지 판별하면 된다.
나는 인덱싱을 통해 dfs를 돌며 모든 숫자 조합들을 매 재귀함수마다 소수인지 판별하였고 중복된 숫자들을 제거하기 위하여 list에 모든 숫자 조합들을 저장하고 중복된 숫자가 없을 때만 정답에 추가하는 코드를 넣었다.

-> 다른 사람의 풀이를 보며 얻은 팁들

1. set

• 집합 관련된 것들을 쉽게 처리하기 위한 파이썬 자료구조
• 특징: 중복을 허용하지 않는다 , 순서가 없다
• 인덱싱을 통한 접근이 불가능하므로 리스트나 튜플로 변환해야함.
• 교집합(&) , 합집합 (|) , 차집합(-) 처리에 용이하다.
• add , update , remove

2. filter()

• list의 element에 대해서 어떤 조건에 만족하는 값만 반환하고 싶을때 사용한다.
• filter(조건함수,리스트)

3. boolean list를 활용한 모든 조합의 재귀함수 호출 => i번째 인덱스 값의 제거 후 재귀함수 호출

• 밑의 코드 참고
• permutation(base + s, array[:i] + array[i+1:])

코드

import math
def isPrime(number):
    if( int(number) == 1 ): return False
    count = 0
    number = int(number)
    for i in range( 1, int(math.sqrt(number))+1 ):
        if( number % i == 0 ):
            count += 1
    return True if count == 1 else False

def solution(numbers):
    answer = 0
    l = []
    v = [0] * len(numbers)
    def dfs(index,number,v):
        new = v[:]
        new[index] = 1
        number += numbers[index]
        if( isPrime(number) ):
            if( int(number) not in l ):
                l.append( int(number) )
        for i in range( len(numbers) ):
            if( not new[i] ):
                dfs(i,number,new)
    for i in range( len(numbers) ):
        dfs(i,"",v)
    return len(l)

• 더욱 효율적인 코드 )

import math
def check_prime(n):
    if n < 2:
        return False

    if n == 2:
        return True

    for i in range(2, int(math.sqrt(n)) + 1):
        if (n % i) == 0:
            return False

    return True

number_set = set()
def permutation(base, array):
    if base:
        number_set.add(int(base))

    for i, s in enumerate(array):
        permutation(base + s, array[:i] + array[i+1:])

def solution(numbers):
    answer = 0

    permutation("", list(numbers))

    answer = len(list(filter(check_prime, number_set)))

    return answer