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

[LV2] 소수 찾기 문제링크 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.  www.programmers.co.kr

 

문제 해설

 

이 문제는 우선 문자열을 각각의 숫자로 자른 후 순열을 통해 숫자를 만들고 각각의 숫자가 소수인지 아닌지를 판단하면 되는 문제이며 소수 판별시에는 효율적인 코드를 작성하기 위해서 에라토스테네스의 체 알고리즘을 사용 하였다.

from itertools import permutations
import math

def isprime(num): #에라토스테네스의 체 알고리즘을 사용한 소수판별 함수
    if num<2:
        return False
    for i in range(2,int(math.sqrt(num))+1):
        if num%i==0:
            return False
    return True

def solution(numbers): 
    numbers=list(numbers) #각각의 문자를 쪼개주기 위해 list형으로 변환
    per=[] #순열을 저장하기 위한 변수(문자형태)
    num=[] #순열을 저장하기 위한 변수(정수형태)
    cnt=0
    for i in range(1,len(numbers)+1): # 순열을 돌려서 모든 경우의 수를 리스트에 저장
        per+=list(permutations(numbers,i))
    for p in per: #리스트에 있는 경우의 수들을 정수로 변환하여 저장 
        tmp=int(''.join(p))
        num.append(tmp)
    num=set(num) #중복된 숫자들 삭제
    for i in num: # 소수판별 함수 사용 만약 소수면 cnt+=1 
        if isprime(i)==True:
            cnt+=1
    return cnt

 

Key Point

 

• 파이썬에서 순열을 구해주는 라이브러리인 permutations를 알고 있어야 한다.
• 에라토스테네스의 체 알고리즘을 인지하고 효율적인 코드를 작성할 수 있어야 한다.