[알고리즘] 프로그래머스 - 소수 찾기

프로그래머스 - 소수 찾기

내 풀이

from itertools import permutations

def solution(numbers):
    answer = 0
    MAX_NUM = 10000000
    prime_list = [True] * MAX_NUM
    visited = [False] * MAX_NUM
    prime_list[0] = False
    prime_list[1] = False

    def erathos():
        for i in range(2, int(MAX_NUM**0.5)+1):
            for j in range(i*2, MAX_NUM, i):
                prime_list[j] = False

    erathos()
    for k in range(1, len(numbers)+1):
        for permu in permutations(numbers, k):
            if prime_list[int(''.join(permu))] and not visited[int(''.join(permu))]:
                visited[int(''.join(permu))] = True
                answer += 1

    return answer

에라토스테네스의 체를 미리 만들고, 가능한 순열의 수를 완전탐색해가며 소수인지 아닌지 확인한다. 이미 방문한 수라면 visited로 걸러낸다.

사실 완전탐색이라고 문제 분류가 되어있지 않았다면 이렇게 풀 시도를 하지 않았을 것이다. 돌려보니 6000ms~7000ms가 나왔다.