Programmers - 소수 찾기(Python)

문제 설명

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

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

제한사항

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

입출력 예

numbersreturn
"17"3
"011"2

입출력 예 설명

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

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

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

✍ 코드

from itertools import permutations
import math

def check(n):
    k = math.sqrt(n)

    if n < 2: 
        return False

    for i in range(2, int(k)+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = []
    for k in range(1, len(numbers)+1):
        perlist = list(map(''.join, permutations(list(numbers), k)))
        for i in list(set(perlist)):
            if check(int(i)):
                answer.append(int(i))

    answer = len(set(answer))

    return answer

numbers = "17"

print(solution(numbers)) # 결과 예 : 3 

풀이 과정
1) check라는 함수를 만들어서 소수를 판정한다. 여기서, math.sqrt를 사용하는 이유는 제곱수의 경우 소수가 아니기 때문에 이를 통해 판정한다.
2) permutations를 이용해서 모든 경우의 수를 만들고 판정한다. 단, 여기서 중복되는 수가 발생해서 set으로 미리 줄이고 하면 속도가 많이 빨라진다.
3) answer에 모든 소수를 집어넣고 길이를 출력하면 정답이 나온다.

📝 결과

😃 느낀점

  • permutations가 있다는 것을 몰랐다. 이것을 알게 되었음에 감사를 느낀다.

👍 Irish의 모든 코드 보기

-> Irish Github

좋은 웹페이지 즐겨찾기