프로그래머스 / 정수론 / 소수 찾기

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

종이 조각에 적힌 숫자들로 만들 수 있는 소수는 몇 개인지 알아내어라.

 

 

적힌 숫자들이 총 7글자이다.

 

7글자를 나열하여 만들 수 있는 숫자들을 어떻게 알 수 있는가?

 

7P1 + 7P2 .. ~ => 13699가 나오게 된다.

from math import perm
total = 0
for i in range(1, 8):
    total += perm(7, i)
print(total)

 

이 코드를 이용하여 알 수 있다.

이로써 모든 가짓수를 돌면서 소수인지 알면 된다.

 

그 후 소수인지 판별하는 것은 O(n^0.5) 방법을 이용하여 구현해주었다.

 

하지만 '011' 과 '11'가 같은 것을 처리해주기 위해서

set 자료형을 이용하여 크기를 리턴해주었다.

 

 

정답코드

---

'''
'25. 12. 22.(월)

1. 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 있을 때 만들 수 있는 소수는 몇 개인가

7P1
7P2
7P3

permutation을 통해서 소수를 찾고
출력한다.
'''
from itertools import permutations as perm
def isPrime(n: int) -> bool:
    if n == 0 or n == 1:return False
    for i in range(2, int(n**.5) + 1):
        if n % i == 0:return False
    return True
def solution(numbers: str):
    answer = 0
    
    number_list = [*numbers]
    
    result = set()
    for i in range(1, len(numbers) + 1):
        for comb in perm(number_list, i):
            str_number = ''.join(comb)
            number = int(str_number)
            
            if isPrime(number):
                result.add(number)
    
    return len(result)

 

깃허브 : https://buly.kr/BeLYPf0

유튜브 : https://youtu.be/j4xVyILT4mY