[프로그래머스] Level2, 소수 찾기 (Python)

문제

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

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

 

코드

from itertools import permutations
import math

def is_prime_number(n):
    if n==0 or n==1:
        return False
    else:
        for i in range(2, int(math.sqrt(n))+1):
            if n % i == 0:
                return False
        return True
    
def solution(numbers):
    answer=[]
    for i in range(1, len(numbers)+1):
        arr = list(permutations(numbers, i)) 
        for j in range(len(arr)):
            num = int(''.join(map(str,arr[j])))
            print(num)
            if is_prime_number(num):
                answer.append(num)
                
    answer=list(set(answer))
    return len(answer)
            

주어진 문자열을 가지고 숫자를 만들어 소수를 몇개 만들 수 있는지 찾는 문제이다.

 

파이썬에서 제공해주는 itertools를 이용해 순열 또는 조합을 사용해야 하는데 숫자에서 17과 71은 다른 숫자이므로 순서가 존재하는 순열을 사용해야한다.

 

그리고 소수찾기에서는 2~sqrt(n) 까지만 찾아서 나눠지지 않으면 없으면 소수이다.

 

같은 수가 나올 수 있기 때문에 마지막에 set으로 중복을 제거해준다.

ex) "011"일 경우 permutations를 돌리면 [('0', '1', '1'), ('0', '1', '1'), ('1', '0', '1'), ('1', '1', '0'), ('1', '0', '1'), ('1', '1', '0')] 이렇게 순열이 나오게 되는데 이것을 num = int(''.join(map(str,arr[j]))) 과정을 거쳐 합치게 되면 중복된 숫자가 만들어지기 때문에 마지막에 set으로 중복제거를 해줘야한다.