소수 찾기

Eunseo·2022년 5월 2일

Python3 algorithm level2 programmers

Programmers

목록 보기

6/9

소수 찾기 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42839

Summary
소수 판별 및 순열 생성 문제

Description

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

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

[제한사항]

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

[입출력 예]

numbers	return
`"17"`	3
`"011"`	2

Checking List

혼자서 문제를 해결

힌트를 보고 해결

답을 보고 해결

My Answer

정확성 : 통과
효율성 : -
해설
1. 재귀문으로 순열 리스트 생성
2. 만들어진 순열 리스트에서 중복을 제거하고, 각 요소가 소수인지 판별
3. 소수이면 1, 아니면 0을 return 하여 정답값에 더해줌

def isPrime(num):
    if num < 2:
        return 0
    elif num == 2:
        return 1
    
    for i in range(2, int(num**0.5)+1):
        if num%i == 0:
            return 0
    return 1
        
def permutation(arr, n):
    result = []
    if n == 0:
        return ' '
    
    for i, elem in enumerate(arr):
        for P in permutation(arr[:i]+arr[i+1:],n-1):
            result += [elem+P]
    return result

def solution(numbers):
    answer = 0
    perms = []
    for i in range(1, len(numbers)+1):
        perms += [int(p) for p in permutation(numbers, i)]
    for p in set(perms):
        answer += isPrime(p)
    return answer

순열 코드 참고

2022년 6월 16일 기준 새로 작성한 풀이
1년 전과 지금을 비교해보면 코드 스타일이 많이 깔끔해진 것 같다 ~^^

from itertools import permutations

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

def solution(numbers):
    answer = 0
    generated = []
    for i in range(1, len(numbers)+1):
        for comb in permutations(numbers, i):
            generated.append(int(''.join(comb)))
    for gn in set(generated):
        if gn not in [0,1] and isPrime(gn):
            answer += 1
    return answer

Answer Sheet

재귀를 사용하여 순열 구현
set() 에 숫자를 바로 추가하여 중복을 제거함

primeSet = set()

def isPrime(number):
    if number in (0, 1):
        return False
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])

def solution(numbers):
    makeCombinations("", numbers)
    answer = len(primeSet)
    return answer

itertools를 활용하여 순열 생성
생성된 순열 set에서 0,1을 제거 후, 에라토스테네스의 체를 적용하여 소수가 아닌 수들을 set에서 제거

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)