소수 찾기

 

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

프로그래머스

문제풀이

1! ~ 7! 까지 모두 더한 결과는 Σ(i=1 to 7) i! = 5913이 된다. 코드 특성상 지수 시간복잡도를 가지게 되지만 n이 최대 7까지만 주어지기 때문에 모든 경우의 순열을 구하고 소수 판별을 진행할 수 있다.

 

해당 문제와 같은 문제들에서 주의해야 할 점은 먼저 주어진 시간 내에 탐색이 가능한지부터 판단을 하고 불가능하다면 그리디 방법을, 그것 또한 불가능하다면 DP를 활용해서 풀이해야 한다.

 

• permutations를 이용하여 1부터 7까지의 모든 순열을 구해준다. permuations는 튜플 형태로 반환하기 때문에 각 반환결과를 이어 붙여서 정수로 변환한 뒤 요소를 배열에 확장해 준다.
• 중복되는 요소가 있을 수 있기 때문에 중복제거를 해준 뒤 n의 제곱근까지만 탐색을 하여 소수 판별을 진행한다.

from itertools import permutations


def solution(numbers):
    answer = 0

    convert = []
    for i in range(1, len(numbers) + 1):
        convert.extend([int("".join(comb)) for comb in permutations(numbers, i)])

    for num in set(convert):
        if primes(num):
            answer += 1

    return answer


def primes(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True