[프로그래머스] 소수 찾기 (파이썬/python)

🎈문제

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

🎁어떤 알고리즘?

순열

경우의 수 문제를 보면 가장 먼저 itertools를 활용할 수 있는 단순한 문제인지, 조건이 까다로워서 백트래킹을 활용해야할 지 파악해야한다. 이 문제의 경우 permutations로 해결할 수 있는 단순한 문제였다.

 

코드 순서

1. permutations를 활용해 모든 경우의 수 찾기

2. 중복 제거하기

3. 만들어낸 숫자 중 소수 개수 찾기 -> 에라토스테네스의 체 활용

 

에라토스테네스의 체

소수를 찾는 문제의 경우 일반적으로 두 가지를 생각할 수 있다. 

1) 13이라는 숫자가 소수인지 판별하는 문제 ( 하나의 소수를 판별하는 문제)

2) 13 미만의 숫자 중 소수를 모두 구하는 문제 ( 다수의 소수를 판별하는 문제)

1번 처럼 하나의 숫자가 소수인지를 판별하기 위해서는 단순히 for i in range(2,13+1) 로 일일이 나눠봄으로써 구해도 상관없지만, 2번 처럼 여러 소수를 구해봐야할 경우 일일이 for문을 돌리면 시간복잡도가 굉장히 증가하게 된다. 따라서 에라토스테네스의 체 알고리즘을 사용해서 소수를 구하는 것이 좋다.(에라토스테네스의 체를 처음 들어본다면 구글에 꼭 검색해보자)

 

from itertools import permutations

def solution(numbers):
    
    answer = 0
    num_lst = []

    # 경우의 수
    for i in range(1,len(numbers)+1):
        for p in permutations(numbers,i):
            num_lst.append(int(''.join(p)))
    
    num_lst = set(num_lst)  # 중복 제거
    
    # 소수 판별, 에라토스테네스의 체 활용
    max_num = max(num_lst)
    temp = [False,False] + [True for _ in range(max_num-1)]
    
    for i in range(2,(int((max_num+1)**0.5))):
        for j in range(i*2,max_num+1,i):
            temp[j] = False
    
    for i in num_lst:
        if temp[i]:
            answer += 1
    
    return answer