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

문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/42839

 

 

📋 문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.

흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

 

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

 

 

👉 입출력

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

 

 

💡 사용된 개념

✔️ itertools.permutations

iterable 요소의 길이 r에 해당하는 순열을 리턴하는 함수이다.

 

itertools.permutations(iterable, r=None)

 

예를 들어 1, 2로 만들 수 있는 숫자는 1, 2, 12, 21이다.

이때 itertools.permutations를 사용하면 r개의 원소를 사용해 순열을 만들 수 있다.

 

from itertools import permutations
arr = [1, 2]

print(list(permutations(arr, 1)))
print(list(permutations(arr, 2)))

# output
# [(1,), (2,)]
# [(1, 2), (2, 1)]

 

 

📝 풀이

from itertools import permutations

def prime_list(n):
  sieve = [True]*(n)
  m = int(n**0.5)
  
  for i in range(2, m+1):
    if sieve[i] == True:
      for j in range(i+i, n, i):
        sieve[j] = False
  return [i for i in range(2, n) if sieve[i] == True]

def solution(numbers):
  arr = list(numbers)
  nums = []
  for i in range(1, len(numbers)+1):
    nums += list(map(int, map(''.join, permutations(arr, i))))
  primeList = prime_list(max(nums)+1)
  
  return len(list(filter(lambda x: int(x) in primeList, set(nums))))

 

주어진 numbers로 숫자를 어떻게 만들지가 어려웠다.

요소들을 순회하면서 하나씩 붙여나가는 수밖에 없나 했을 때 혹시나 해서 찾아보니 파이썬에 순열을 구하는 방법이 있었다.

파이썬처럼 아는 만큼 편해지는 언어는 없는 것 같다.

 

문제의 풀이는 다음과 같다.

먼저 numbers를 리스트로 만들어 arr에 저장한다.

이후 1에서 numbers의 길이 + 1만큼 for문을 돌며 각 자릿수에 해당하는 순열을 만들고 이를 nums에 저장한다.

for문이 끝나면 nums는 numbers의 요소들로 만들 수 있는 모든 숫자가 들어있다.

 

2 ~ max(nums)까지의 소수 리스트를 구하기 위해 prime_list 함수에 nums의 최댓값 + 1을 넘긴다.

prime_list 함수는 에라토스테네스의 체를 이용했다.

prime_list의 리턴값은 2 ~ max(nums)까지의 숫자 중 소수만 담긴 리스트이다.

이 소수 리스트를 primeList에 저장했다.

 

종이 조각으로 만들 수 있는 소수가 몇 개인지 구하는 문제였으므로 set으로 중복을 제거한 nums의 요소들 중 primeList에 있는 것들만 filter 함수로 모은 뒤 이 리스트의 길이를 리턴한다.

 

 

 

🔍 참조

itertools.permutations https://programmers.co.kr/learn/courses/4008/lessons/12836

itertools.permutations https://wikidocs.net/109282