[프로그래머스/Level2/파이썬3(python3)] 소수 찾기

[프로그래머스/Level2/파이썬3(python3)] 소수 찾기

문제

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

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

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

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

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

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

풀이

from itertools import permutations


def solution(numbers):
    answer = 0
    already_checked = set()
    for i in range(1, len(numbers) + 1):
        for cmb in list(permutations(numbers, i)):
            number = int(''.join(cmb))
            if number in already_checked:
                continue
            already_checked.add(number)
            current_number_prime = True
            for j in range(2, int(number ** 0.5) + 1):
                if number % j == 0:
                    current_number_prime = False
            if number != 1 and number != 0 and current_number_prime:
                answer += 1
    return answer

설명

저번에 소수만들기 문제를 풀 때 썼던 itertools의 combinations가 생각났다. 해당 함수는 iterable한 자료형이 주어졌을 때 두번째 인수로 들어온 수만큼 선택하는 모든 경우의 수를 리턴해주는 거였는데 이런 기능을 제공한다면 분명히 순서도 섞은 경우의 수도 리턴해주는 게 있을 거라 생각했다. 찾아봤더니 당연히 있었다. 우리나라 수학 용어로는 combination이 조합, permutation은 순열을 의미한다. 경우의 수를 배울 때 배웠던 게 기억이 난다.
 이 문제에서 "17"이 주어졌다 하더라도 17과 71은 다른 숫자이기 떄문에 순열을 적용하는 것이 맞다. 그리고 단순 주어진 숫자들의 배치뿐만이 아닌 사용되는 숫자의 개수도 고려해야 한다. 코드의 흐름은 다음과 같다.

 

1. 종이조각의 개수를 구한다.
2. 해당 종이조각으로 만들 수 있는 모든 수조합을 구한다.
3. 수조합이 소수인지 아닌지 검사하고 소수면 answer에 1을 더한다. 대신 전에 검사했던 수조합과 동일한 수조합일 경우에는 검사하지 않고 넘긴다.

사용하는 종이조각의 개수에 따라서도 많은 수조합이 새로 생성되기 때문에 이런식으로 구현했는데 3중 for문이라는 점이 뭔가 석연치 않다. 근데 다른 풀이를 봐도 어쩔 수 없는 부분인 것 같다.