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

문제

문제 링크

문제 설명

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

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

제한 사항

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

입출력 예

numbers	return
"17"	3
"011"	2

소수 찾기 알고리즘

# 소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임

• 위에는 기본적인 소수 찾기는 알고리즘 코드이다.
• 기본적으로 2부터 나보다 작은 수까지 중에서 나누어떨어지는 것이 없으면 소수로 본다.
• 여기서 만약 0이나 1이 들어올 수 있다면 그것을 제한해주는 알고리즘이 필요하다.

순열 구하기

• python 에서는 Itertools 라이브러리에서 순열과 조합을 쉽게 구할 수 있다. 관련된 설명은 참고 블로그에서 확인할 수 있다.
• 일단 문제에서 numbers의 크기가 7 이하이기 때문에 모든 경우의 수를 다 조합해서 찾아보도록 하는 것이 필요하다. 그리고 숫자의 순서도 고려해야 하기 때문에 permutations를 사용하였다.

정답 코드

from itertools import permutations

def is_prime(num):
    if num == 1 or num == 0:
        return False
    for i in range(2, num):
        if num % i == 0 :
            return False
    return True
    
def solution(numbers):
    answer = 0
    prime = []
    paper = [i for i in numbers]
    for k in range(1, len(paper)+1):
        permut = list(permutations(paper, k))
        permut_nums = list(set([int(''.join(i)) for i in permut]))
        for num in permut_nums:
            if is_prime(num):
                if num not in prime:
                    answer += 1
                    prime.append(num)
    return answer

• 리스트 안에 0이나 1이 들어있을 수 있기 때문에 is_prime에서 0이나 1은 False로 반환하게 하였다.
• numbers를 한자리 숫자의 리스트로 바꾸어 준 뒤
• 1개부터 7개까지의 조합을 뽑아낸다.
• 순열을 뽑고 나서 중복이 있을 수 있으므로 set으로 한 번 중복을 제거해준다.
• permut nums가 소수가 맞는지 확인하고, 소수에 집어넣어서 중복 없이 계산할 수 있또록 하여 answer를 반환한다.

느낀 점

• 순열 구하는 라이브러리만 잘 알고 있으면 무리 없이 풀 수 있는 문제였다.