프로그래머스 | Lv.2 소수찾기 (파이썬)

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

풀이

(1) 순열+소수찾기(2부터 n-1)까지 나누기

테스트케이스 일부는 통과하지만 대부분의 테스트케이스에서 실패가 떴다.

또한 실행 시간도 매우 오래 걸림

 

from itertools import permutations

def solution(numbers):
    answer = []
    n = len(numbers)
    nums = [i for i in numbers]
    pers = []
    for i in range(1, n+1):
        pers += list(permutations(nums, i))
    new_nums = [int(('').join(p)) for p in pers]

    #소수인지 판별 방법 2부터 n-1까지 나눠서 나머지가 0인 순간이 한번이라도 없어야됨
    for i in new_nums:
        for j in range(2, len(new_nums)):
            if i>1 and i not in answer:
                if i%j == 0:
                    break
                else:
                    answer.append(i)

    return len(answer)

(2) 소수를 판별하는 또 다른 방법은 해당 수의 제곱근까지만 나눠보는 방법이다.

n의 약수의 갯수는 n/2개를 넘지 못하고 n의 약수가 존재한다면 절반은 제곱근까지의 범위에 존재한다.

따라서 n**0.5 까지 나눠보고 판별한다.

from itertools import permutations

def solution(numbers):
    answer = []
    nums = [i for i in numbers]
    pers = []
    for i in range(1, len(numbers)+1):
        pers += list(permutations(nums, i))
    new_nums = [int(('').join(p)) for p in pers]

    #소수인지 판별 방법 
    # 1. 2부터 n-1까지 나눠서 나머지가 0인 순간이 한번이라도 없어야됨(시간 초과)
    # 2. 제곱근까지만 나눠본다.
    check = True
    for n in new_nums:
        if n < 2:
            continue
        check = True
        for i in range(2, int(n**0.5) +1):
            if n%i == 0:
                check = False
                break
        if check:
            answer.append(n)

    return len(set(answer))