[프로그래머스]코딩테스트 연습완전탐색 소수 찾기

문제

문제 설명

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

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

제한사항

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

 

입력 & 출력

입출력 예

numbersreturn

"17"	3
"011"	2

새로 사용한 함수

permutations() : 배열의 여러 가지 조합을 만들어주는 함수 

 

풀이 과정

1. 문제내에서 소수를 판별하는 부분이 있기 때문에 소수 판별하는 함수는 다른 짜인 내용을 참고하였습니다. 해당 함수에서는 주어진 숫자의 절반에 1을 더한 범위까지 하였지만 에라토스테네스의 체의 법칙을 생각해 본다면 num의 제곱근 + 1, num**1/2+1으로 변경하여도 문제가 없을 것이라는 생각을 합니다.

2. 소수 판별하는 함수를 구성하여두었으니 입력받은 문자열을 여러조합으로 만드는 것이 필요합니다. 문자열을 배열로 나타내기 위해서는 list()에 해당 문자열을 넣어줍니다.

3. 이 상태로 조합을 위하여 내장함수임 permutations를 이용합니다. 여기서는 문자열의 조합을 만들어주기 때문에. join을 이용하여 문자열을 붙여주고 이것을 또 map함수를 이용하여 int형으로 형 변환시켜주는 과정이 필요합니다.

4. 3의 과정을 거친 숫자를 result라는 변수에 넣어줍니다 이것은 숫자로 이루어진 배열이 되는데 numbers를 길이 만큼 수행하기 때문에 길이가 1일 때의 배열 2일 때의 배열... 문자열 최대길이까지의 배열을 하나로 합친 배열인 check 배열에 append 해주게 됩니다.

5. 문자열의 구조에 따라 4번 과정에서 중복이 생길수가 있는데 중복된 숫자는 같은 것으로 생각할 수 있기 때문에 set() 조합 함수를 이용하여 중복 제거를 수행하면 입력받은 숫자로 만들 수 있는 숫자의 조합이 만들어지게 됩니다.

6. 5번에서 만든 숫자를 하나씩 빼내어서 소수 판별 함수로 판별하고 True일 경우에 answer값을 1씩 증가시키고 이를 리턴하여 주면 원하는 결괏값을 얻을 수 있습니다.

 

코드

from itertools import permutations

"""소수 판별 함수"""


def is_prime_number(num):
    if num == 0 or num == 1:
        return False
    else:
        for n in range(2, (num // 2) + 1):  # math를 사용하지 않고 (num//2)+1 까지로 설정
            if num % n == 0:
                return False

        return True


def solution(numbers):
    # prime_set = set()
    answer = 0
    check = []
    for i in range(len(numbers)):
        numbers_permutation = permutations(list(numbers), i + 1)
        result = list(map(int, map("".join, numbers_permutation)))

        for ch in result:
            check.append(ch)

        print(set(check))
    set_check = set(check)
    for check in set_check:
        if is_prime_number(check):
            answer += 1

    return answer


print(solution("011"))