Level 2. 소수 찾기

09. 소수 찾기

코딩테스트 연습 > 완전탐색 > 소수 찾기
https://programmers.co.kr/learn/courses/30/lessons/42839

---

문제 설명

Input value =

• numbers = 숫자로 이루어진 문자열

Process =

• 하나 이상의 문자열의 원소를 나열하여 숫자 생성

• 생성된 숫자가 소수인지 판단 여부

Output value =

• return = 생성된 숫자 중 소수의 갯수

---

제한 사항

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

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

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

---

문제 구상

1. 처음에는 빈 리스트를 만든 후 permutation을 range(1,len(numbers)+1)만큼 반복하여 append() 한 뒤, ''.join을 거쳐 set값으로 바꾸는 방법을 사용하였다.

for i in range(1,len(numbers)+1):
    array += list(permutations(numbers,i))
answer = []
for a in array:
    a = ''.join(a)
    answer.append(a)
num = set(int(i) for i in answer)

2. 그 후 소수를 찾는 함수를 정의하였다.

numbers = '011'
def prime_number(n):
    if n==0 or n==1:
        return False
    else:
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0:
                return False        
        return True 

3. 이후 1번에서 만든 num의 원소들을 소수찾는 함수로 필터링하여 최종 값을 구하였다.

result = []
for i in num:
    if prime_number(i):
        result.append(i)
len(result)

이후 다른 풀이를 참고하여 처음부터 set()을 이용한 방법을 알게되었으며,이를 통한 풀이는 다음과 같다!

#00
numbers = '011'
#01
from itertools import permutations
set_ = set()
for n in range(len(numbers)):
    set_ |= set(map(int,map(''.join,permutations(list(numbers),n+1))))
#02
    set_-=set(range(0,2))
#03
for i in range(2,int(max(set_)**0.5)+1):
    set_-=set(range(i*2,max(set_)+1,i))

---

문제 풀이

구상한 방법을 바탕으로 통과한 첫번째 풀이는 다음과 같다...너무 막코딩이지만..

from itertools import permutations
from math import sqrt

def prime_number(n):
    if n==0 or n==1:
        return False
    else:
        for i in range(2, int(sqrt(n)) + 1):
            if n % i == 0:
                return False        
        return True 
def solution(numbers):
    array = []
    for i in range(1,len(numbers)+1):
        array += list(permutations(numbers,i))
    answer = []
    for a in array:
        a = ''.join(a)
        answer.append(a)
    num = list(int(i) for i in answer)
    result = []
    for i in num:
        if is_prime_number(i):
            result.append(i)
    return len(result)