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

📝 문제 설명

한자리 숫자가 적힌 종이 조각들이 흩어져 있다.

각 종이 조각의 숫자 조합으로 소수를 몇 개 만들 수 있는지 알아내려 한다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때,
만들 수 있는 숫자가 몇 개인지 그 값을 return한다.

📝 제한 조건

numbers는 길이 1이상 7이하인 문자열이다.

numbers는 0~9까지의 숫자만으로 이루어져 있다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미이다.

💻 코드

import itertools
import math

def solution(numbers):
    # casting
    numbers_list = list(numbers)
    
    # permutation
    nPr = []
    for i in range(1, len(numbers_list)+1):
        permut = list(set(itertools.permutations(numbers_list, i)))
        for j in range(0, len(permut)):
            nPr.append(int("".join(permut[j])))
    nPr = list(set(nPr))
    
    # count
    cnt = 0
    for n in nPr:
        if prime_number(n) == True:
            cnt += 1
    
    answer = cnt
    return answer

def prime_number(n):
    # discrimination
    D = True
    sqrt_n = int(math.sqrt(n))
    if n==0 or n==1:
        D = False
    if sqrt_n >= 2:
        for k in range(2, sqrt_n+1):
            if n%k == 0:
                D = False
                break
    return D

📌 casting

주어진 numbers는 하나의 문자열이기 때문에 각각의 숫자로 보기 위하여,
각각의 문자열로 캐스팅해주었다.

📌 permutation

문제접근방식으로 가장 먼저 각각의 숫자로 만들 수 있는 경우의 수를 생각했다.

"17"이 주어졌을 때, 17과 71은 다른 숫자(다른 경우)이므로,
순서를 고려한 순열을 itertools를 통해 배열로 놓았다.

숫자 1개를 뽑는 경우부터 numbers_list내의 숫자를 다 뽑는 경우까지,
for문을 통해 변수 r값에 대한 경우를 구하였다.

"011"이 주어졌을 때, itertools에서 각각의 1을 개별객체로 인식하므로 set으로 중복제거 해주었다.

join과 append를 통해 하나의 숫자로 nPr에 들어가도록 하였으며,
"01"과 "1"의 경우 중복된 숫자이므로 set으로 중복제거 해주었다.

📌 count(answer)

for문을 통해 nPr의 각 숫자에 대해, prime_number(n)가 참이면
count하였다.

📌 discrimination

숫자 n이 input으로 주어졌을 때,
0과 1인 경우와 주어진 범위에서 약수가 존재하는 경우
False가 반환되도록 했다.

💡 runtime

2가지 상황 변수에 대해 런타임을 생각해보았다.

nPr에서 set을 써주지만 permut에서 set을 추가적으로 써줄때와
prime_number(n)에서 range범위를 n까지 도는것이 아닌,
sqrt_n까지 도는 경우를 비교해보았다.

set:X, sqrt:X >>

set:O, sqrt:X >>

set:X, sqrt:O >>

set:O, sqrt:O >>

비교결과 sqrt를 써주는 것이 런타임을 줄일 수 있는 확실한 방법임을 확인했다.

prime_number(n)을 통해 소수판별시,
시간복잡도가 O(n)에서 O(√n)으로 바뀌기 때문인 것으로 사료된다.