소수 찾기

프로그래머스 - 소수 찾기

문제 설명

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

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

제한 사항

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

입출력 예

접근

우선 문자열의 한 글자씩 가져오면서 전에 검사했던 적이 없는 숫자라면 소수인지 판별해 소수인 경우의 개수를 저장한다.

이렇게, 한 자리 수의 경우는 소수를 판별하는 것이 가능한데, 두 개 이상의 수를 조합하였을 때 생기는 모든 수를 어떻게 구할 수 있는지를 모르겠어서 다른 사람의 풀이를 살펴봤다.

다른 사람의 풀이

from itertools import permutations
import math

def check(n):
    k = math.sqrt(n)
    if n < 2: 
        return False

    for i in range(2, int(k)+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = []
    for k in range(1, len(numbers)+1):
        perlist = list(map(''.join, permutations(list(numbers), k)))
        for i in list(set(perlist)):
            if check(int(i)):
                answer.append(int(i))

    answer = len(set(answer))

    return answer

[프로그래머스] 소수 찾기 / 파이썬 - 초코 김현우

우선 check 함수는 나도 이 알고리즘을 해결하기 위해 필요하다 생각해 구현을 해 둔 상황이었다. 막혔던 부분을 해결하는데 permutations를 이용한다는 것이 중요한 포인트인 것 같았다.

permutations는 순열의 영어인 "permutation"에서 유측할 수 있듯이 주어진 리터럴에서 두 번째 인자로 전달된 수만큼 고르는 순열의 모든 경우를 구해 permutations 리터럴로 반환한다.

반환된 값을 단순히 list로 만들면 조합 가능한 경우를 set으로 묶어 요소를 만드는 것을 볼 수 있다. 문제를 해결하기 위해서는 set의 요소들을 하나로 묶을 필요가 있기 때문에 ''.join으로 맵핑함으로써 하나의 문자열을 구한다.

이후, 해당 결과를 set으로 중복을 제거하여 각 요소를 검사해 소수인 경우 배열에 넣는다. 다만, 0으로 인해 조합한 결과가 같을 수 있으므로 마지막에 answer 내의 요소들의 중복을 제거한 뒤에 남은 요소의 수를 반환하면 정답을 구할 수 있다.