[프로그래머스-레벨2]소수 찾기 - python

iamjinseo·2022년 9월 26일

소수 에라토스테네스의 체 완전탐색 프로그래머스

문제풀이-Python

목록 보기

103/134

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

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

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

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

시도

1

from itertools import permutations as per
def solution(numbers):
    # numbers의 숫자로 이루어지는 모둔 순열
    ans = list(per(numbers))
    
    # 단일 숫자
    for n in numbers:
        ans.append(n)
    
    # 조합된 숫자 합쳐서 숫자 만들기
    nums = []
    for ns in ans:
        s = ""
        for n in ns:
            s += n
        nums.append(int(s))
    
    nums = set(nums) #중복제거
    
    res = 0
    # 소수 판별
    for n in nums:
        if n == 1 or n == 0 : continue
        if isPrime(n):
            res += 1
    return res

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

결과

실행시간이 너무 김

순열을 구하는 데다가 일일이 isPrime()호출해대니 오래걸리는 것 같음

최종 풀이

조합된 숫자 합쳐서 숫자 만들기 부분이 좀 허술한데 "".join()으로 쉽게 해결 가능
join()을 오래 안써서 그런지 생각을 못했다
```
# 조합된 숫자 합쳐서 숫자 만들기
nums = set()
for n in ans:
    nums.add(int("".join(n)))
```
소수 판별 부분에서 범위를 숫자의 제곱근까지 해야함.
만약에 숫자가 20이면 제곱근은 4.xxx 니까 2~4의 숫자로 20을 나눠보면 됨 (20의 약수는 1, 2, 4, 5, 20)
"111" 이 있을 때 결과는 1이어야 하는데 0이 나옴
3-1. 내 알고리즘으로 조합했을 때 {1, 111}만 나옴. 알고보니 permutations()만으로는 모든 개수의 순열조합을 구할 수 없음
=> 반복문 돌리면서 1개~문자열개수만큼의 순열 생성

from itertools import permutations as per
def solution(numbers):
    # numbers의 숫자로 이루어지는 모둔 순열
    ans = set()
    for i in range(1, len(numbers)+1):
        ans.add(per(numbers, i))
    # print(ans)
    
    # 조합된 숫자 합쳐서 숫자 만들기
    nums = set()
    for ns in ans:
        for n in ns: 
            nums.add(int("".join(n)))
    
    res = 0
    # 소수 판별
    for n in nums:
        if n < 2 : continue
        if isPrime(n):
            res += 1
    return res

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

결과

남의 코드

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)