프로그래머스 (Level 2) - 소수 찾기

1. 문제 설명

• 한자리 숫자가 적힌 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려고 한다.
• 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어진다.
• 종이 조각으로 만들 수 있는 소수가 몇 개 인지 return

---

2. 제한사항

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

3. 입출력 예

numbers	return
"17"	3
"011"	2

• [1,7] 으로는 소수 [7, 17, 71]를 만들 수 있다.
• [0,1,1]으로는 소수 [11, 101]를 만들 수 있다.
  • 11과 011은 같은 숫자로 취급한다.

---

4. 풀이 접근

1. 문자열로 입력 받았으므로 하나씩 숫자를 뜯어내자
2. 각 조합하여 만들 수 있는 모든 수를 구해야 하므로 순열을 이용해서 모든 수를 구하자.
   1. from itertools import permutations
3. 순열로 만들어진 문자열을 정수형으로 바꿔주자
4. 만들어진 모든 수를 자기 자신외에 나눠지는지 소수를 구한다.
5. 복수의 숫자가 만들어질 수 있으므로 중복제거한다.

---

5. 코드

from itertools import permutations

def solution(numbers):
    
    a = list(numbers)
    a_list = []
    answer = []

    for i in range(1, len(a)+1):
        a_list += list(permutations(a, i)) #i자리수 만큼 순열 생성

    result = [int(("").join(key)) for key in a_list] #숫자로 변경하기

    for number in result: #모든 경우의 수 하나씩 확인하며
        TF = True #소수 판별을 위한 boolean 형
        if(number <2): #1은 소수가 아니므로
            continue

        for count in range(2,number-1): #자기 자신 외에 나눠지는 것이 있는지 확인
            if(number % count == 0): #만일 나눠떨어지면 소수가 아님
                TF = False
                break

        if(TF == True): #소수일 경우
            answer.append(number)

    return len(set(answer)) #중복방지

• permutations 처음 반복문에서는 a의 숫자에 대해 i 자리수 만큼 모든 순열을 생성해서 a_list에 모두 넣어준다.
• result에는 만들어진 순열들을 하나의 정수형으로 변경했다.
• 소수 판별을 위한 TF라는 boolean형을 만들어 줬다.
• 중복 방지를 위해 set자료형을 사용했다.

---

6. 알아둘만한 문법

from itertools import permutations

numbers = "17"

a = list(numbers)
a_list = []
    
for i in range(1, len(a)+1):
    a_list += list(permutations(a, i)) #i자리수 만큼 순열 생성

#출력 결과
[('1',), ('7',), ('1', '7'), ('7', '1')]

• 순열인 permutaions으로 1과 7에대한 모든 경우의 수를 만들 수 있다.

 

result = [int(("").join(key)) for key in a_list] #숫자로 변경하기

#출력 결과
[1, 7, 17, 71]

• 리스트안에서 순열로인해 약간 지저분하게? 만들어진 문자열을 (정수일 경우는 이쁘게 나옴) 정수형으로 변경