(Week4)[완전탐색/순열] 소수 찾기

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 30분

1. 문제 설명

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

프로그래머스

한 자리 숫자가 적힌 종이조각들을 붙여서 소수를 몇 개 만들 수 있는지 알아내는 방법

2. 접근 방식

• 소수 판별 함수를 만든다. 
• number들의 조합을 만들어서, 각 수에 대해 소수 판별을 진행한다.
• answer에서 True/False를 구분해서 answer에서 True인 것들만 리턴한다.  

3. 코드

from itertools import permutations
def prime(n):
    if n in (0, 1):
        return False
    for i in range(2, int(n**(1/2))+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    num_ls = []
    for i in range(1, len(numbers)+1):
        num_ls.extend(list(permutations(numbers, i)))
    answer_ls = list(set([int("".join(x)) for x in num_ls[1:]]))
    answer = list(map(prime, answer_ls))
    return answer.count(True)

4. 코멘트

• 순열 시 소수 판별 함수를 계속해서 구해야하기 때문에 시간복잡도에 걸릴 수도 있을 것 같다. 해당 문제의 경우 숫자의 개수가 9개이기 때문에 괜찮았지만, 나중에 더 커지면 효율성이 떨어질 수도 있다. 
• 따라서 DP를 활용해서 max순열 숫자만큼 소수를 구해서 한번만 계산해, 리스트에서 참고할 수 있게 한다면 효율성을 조금 더 챙길 수 있어 보인다.