211112 - 소수 찾기

◾ 소수 찾기 : 프로그래머스 LEVEL 2

• https://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. 해설

• 가능한 모든 경우를 탐색하여 해결할 수 있다.
• permutations 함수를 통해 1개 ~ len(numbers)개를 뽑는 경우를 찾을 수 있다.
• 각 경우가 소수인지 검사하여 소수의 개수를 반환한다.
• 숫자가 중복될 수 있으므로 set() 또는 in, not in 등을 활용하여 구분해야한다.

---

2. 프로그램

1. 소수, 비소수를 담을 리스트 선언
2. range(1 ~ len(numbers) + 1)을 반복하며 모든 경우 탐색
3. int(' '.join(경우의 수))로 정수로 변환
4. 리스트에 담겨있지 않은 수라면 소수인지 확인
   • 소수라면 prime_nums에 추가
   • 소수가 아니라면 not_nums에 추가
5. len(prime_nums)을 통해 소수의 개수 반환

# 코드
from itertools import permutations
def solution(numbers):
    answer = 0

    # numbers에는 같은 숫자가 반복될 수 있으므로
    # 완성된 수를 검사 후 리스트에 담아준다.
    prime_nums = []   # 소수인 경우
    not_nums = [0, 1]   # 소수가 아닌 경우
                        # 0, 1은 기본적으로 소수가 될 수 없다.
                        
    # 1개를 뽑는 경우 ~ len(numbers)개를 뽑는 경우를 모두 조사한다.
    for i in range(1, len(numbers) + 1):    
        # permutations로 모든 경우를 찾는다.
        for p_nums in permutations(numbers, i):
            # join으로 연결 후 int형으로 변환
            val = int(''.join(p_nums))
            flag = True
            # prime_nums, not_nums에 포함되지 않은 경우 소수인지 확인
            if val not in prime_nums and val not in not_nums:
                for j in range(2, val // 2 + 1):
                    if val % j == 0:
                        flag = False
                        break
                # 소수인 경우 prime_nums에 추가
                if flag:
                    prime_nums.append(val)
                # 소수가 아닌 경우 not_nums에 추가
                else:
                    not_nums.append(val)
                    
    # (prime_nums의 길이) : 소수의 개수
    answer = len(prime_nums)

    return answer

• 결과