[Python] 프로그래머스 문제풀이 - 소수 찾기

[Python]프로그래머스 문제풀이 - 소수 찾기

---

서문

오늘은 프로그래머스 사이트 / 코딩테스트 / 완전탐색 부분 세 번째 문제풀이를 하겠습니다. 문제를 살펴보겠습니다. 😉

• 프로그래머스 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42839

코드의 전개 논리가 궁금하시다면, 밑의 사이트에 들어가서 코드를 작성하여 visualize해주시면 코드가 어떤 식으로 흘러가는지 눈으로 파악하실 수 있습니다!

• 파이썬 튜터 사이트 : http://pythontutor.com/visualize.html#mode=display

출처: http://pythontutor.com/

1. 문제 설명

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

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

2. 제한사항

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

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

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

3. 입출력 예 설명

numbers	return
17	3
011	2

#1

• [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

#2

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

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

---

본문

요약

• 숫자가 주어지고 그 숫자의 조합을 모두 구한다.

• 조합의 숫자가 소수인지 판단하여 answer에 소수의 개수를 담아서 출력하라.

문제풀이

코드

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

def solution(num):
    from itertools import permutations

    answer = 0
    list_com = list(num)

    for i in range(2,len(num)+1):
        permutations_list = list(permutations(num, i))

        for j in permutations_list:
            list_com.append(''.join(j))

    list_com = list(set([int(x) for x in list_com]))

    for i in list_com:
        if isPrime(i):
            answer += 1
        else:
            pass

    return answer

결과

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

Detail Code Review

• 소수를 판단하기 위한 함수를 만들어준다. isPrime함수는 에라토스테네스의 체를 구현한 것이다.

• itertools에 있는 permutations함수를 사용하여 numbers의 조합을 구해준다.
  • permutations(num , 2)라고 하면 num을 2개의 순열로 만들어준다. 예컨대 12라고 하면 [('1', '2'), ('2', '1')] 이런 식으로 된다.

• 제한조건 중 "011"와 "11"은 같은 값으로 취급한다는 조항을 [int(x) for x in list_com] 으로 해결한다. 예컨대 "011"을 int로 바꾸면 11로 된다.

• 그 값을 set을 이용하여 중복제거해준 다음 다시 리스트에 담는다.

• 리스트를 돌면서 아까 만든 isPrime함수를 통해 소수일 때 answer에 += 1을 해준다.

---

혹시 문제가 있는 부분이 있으시면 말씀해주세요. 더 좋은 아이디어도 알려주시면 감사하겠습니다.😉