[프로그래머스] 소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

내 풀이

import itertools

def solution(numbers):
    total = []
    for i in range(1, len(numbers)+1):
        step = itertools.permutations(numbers, i)
        for s in step:
            total.append(s)
            
    total1 = list(set([int(''.join(x)) for x in total]))   

    if 1 in total1:
        total1.remove(1)
    if 0 in total1:
        total1.remove(0)
        
    answer = []
    for x in total1:
        prime = []
        for i in range(2, x):
            if x%i == 0:
                prime.append(i)
            else:
                pass
        if len(prime)==0:
            answer.append(x)
        else:
            pass
    return len(answer)
    
print(solution('011'))

위는 기능을 옳게 구현하기는 했지만 시간 초과가 뜬 풀이. 아래는 에라토스테네스의 체 알고리즘을 이용하여 시간 초과 없이 정답을 받은 풀이. (설명은 코멘트 참조)

import itertools

def solution(numbers):
  total = []
  for i in range(1, len(numbers)+1):
      step = itertools.permutations(numbers, i)
      for s in step:
          total.append(s)
              
  total1 = list(set([int(''.join(x)) for x in total]))   

  max1 = max(total1)

  eratosthenes = [False,False] + [True]*(max1-1)

  primes=[]

  for i in range(2,max1+1):
    if eratosthenes[i]:
      primes.append(i)
      for j in range(2*i, max1+1, i):
          eratosthenes[j] = False
          
  answer = [x for x in total1 if x in primes]

  return len(answer)

#print(solution('17'))

코멘트

처음 풀이에서는 주어진 숫자들로 만들 수 있는 수들을 조합을 이용해 만들고 이 수들을 2~N까지 나누어보면서 나누어지는 수가 있다면 (N%i==0 → 나머지가 0) 소수가 아니고, 나누어지는 수가 없다면 소수이므로 return하게 만들었다.
정답은 맞았으나 너무 비효율적인 연산인지 몇몇 케이스에서는 시간 초과가 떴다.

그래서 여러 개의 소수를 찾는데에는 에라토스테네스의 체 알고리즘이 효율적이라고 하여 이 알고리즘을 적용해 보았다. 이 알고리즘은 특정 범위까지의 수들 중 소수만 뽑아내준다. 따라서 내가 가진 숫자들이 소수인지를 금방 알아낼 수 있고, 이것으로 시간 초과 없이 정답을 받았다. 이래서 알고리즘 공부가 중요한가 보다...

References

https://school.programmers.co.kr/learn/courses/30/parts/12230
https://velog.io/@seulki971227/프로그래머스-Lv.1-소수찾기-Python
https://wikidocs.net/21638