[프로그래머스] '소수 찾기' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

 

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

 

 

제한사항

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

 

 

입출력 예

numbers	return
"17"	3
"011"	2

알고리즘 분석

 

• 나의 풀이

from itertools import permutations
def sosu(n): # 소수이면 True, 아니라면 False를 반환 
    if n == 0 or n == 1: return False
    for i in range(2,n//2+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    asets = []
    n_len = len(numbers)
    for i in range(1, n_len+1):
    	# permutations를 이용하여 numbers의 순열을 구해서 asets에 더해줌
        asets += permutations(numbers, i)
    asets = set(map(lambda x: int(''.join(x)), asets)) # 중복을 제거하기 위해 set 자료형으로 변형 
    for aset in asets: # 중복이 제거된 asets의 요소를 확인 
        if sosu(aset): # 소수인지 확인
            answer += 1
    return answer

 

 

• Most1의 풀이

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
    	# 위의 풀이와 마찬가지로 permutations를 이용해 순열을 a에 더해줌(set으로 인해 중복X)
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2)) # a에서 0과 1을 제거 
     # 에라토스테네스의 체를 이용하여 배열 a의 요소 중 가장 큰 수의 사이에 있는 모든 소수를 a에서 제거
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

 

 

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

코딩테스트 연습 - 소수 찾기