Level 2 소수 찾기 Python3

https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3 

코딩테스트 연습 - 소수 찾기

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_소수찾기.py

hwayeon351/Programmers-Algorithms

from itertools import permutations
from math import sqrt
def solution(numbers):
    sosu = set()
    for i in range(1,len(numbers)+1):
        for c in permutations(list(numbers), i):
            num = int("".join(list(c)))
            if num == 1 or num == 0: continue
            check = True
            for n in range(2,int(sqrt(num))+1):
                if num % n == 0:
                    check = False
                    break
            if check==False: continue
            sosu.add(num)
    return len(sosu)

---

풀이 과정 

풀이 시간 24분

이 문제는 문자열 numbers로부터 주어진 숫자들을 조합하여 만들 수 있는 가능한 수들 중에서 소수가 몇 개인지 return하는 문제이다.

따라서 모든 조합을 만든 후에 각각 소수를 판별해줘야 하기 때문에 완전 탐색 알고리즘으로 문제를 풀었다. 그 중 for와 if문을 사용하는 Brute-force serch 알고리즘을 사용하였다. 문제에서 numbers의 길이는 1이상 7이하라고 되어있기 때문에 가능한 숫자의 조합이 최대인 경우 7!이기 때문에 완전 탐색으로 풀이 가능하다고 판단하였다.

from itertools import permutations
from math import sqrt
def solution(numbers):
    #1. 소수 집합 초기화
    sosu = set()
    #2. 가능한 모든 소수 생성 | 시간복잡도 = O(N!)
    for i in range(1,len(numbers)+1):
        for c in permutations(list(numbers), i):
            num = int("".join(list(c)))
            #3. 소수 판별
            if num == 1 or num == 0: continue
            check = True
            for n in range(2,int(sqrt(num))+1):
                if num % n == 0:
                    check = False
                    break
            if check==False: continue
            sosu.add(num)
    return len(sosu)
#순열
#시간복잡도 = O(N!),공간복잡도 = O(N)