[Level 2] 소수 찾기

programmers.co.kr/learn/courses/30/lessons/42839

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

---

접근

처음에 접근했던 방식은 주어진 숫자 중 최댓값을 생성하여 2부터 최댓값까지 탐색하여 소수일 때 입력된 숫자 안에 포함되는지 확인하려고 했다. 하지만 몇몇 케이스에서 시간초과가 발생하였다.

 

그래서 주어진 숫자에서 만들 수 있는 수를 만들어 소수를 판별하고자 하였다.

 

구현

permutations를 통해 1부터 입력된 숫자의 길이만큼의 순열을 만들어준다.

생성된 수가 2이상일 때 소수인지 판별을 하며 2부터 생성된 수-1까지 검사하여 나누어 떨어진다면 break를 하여 시간을 단축하였다. 만약 나누어 떨어지는 것이 없다면 prime_list에 추가한다. 

이후 최종해에는 set으로 중복된 수를 제거하고 그 길이를 대입해준다.

from itertools import permutations
def solution(numbers):
    answer = 0
    prime_list = []
    
    for i in range(1, len(numbers)+1):
        for n in permutations(numbers, i):
            num = ''.join(n)
            num = int(num)
            cnt = 0
            if num <= 1:
                continue
            for k in range(2, num):
                if num%k == 0:
                    break
            else:
                prime_list.append(num)
    prime = set(prime_list)
    answer = len(prime)
            
    return answer