[프로그래머스 level2] 소수 찾기

원래 알고리즘은 깃헙에만 업로드 했지만 기록용으로 벨로그에도 업로드를 해야겠다.

오늘 알고리즘 스터디하는 날인데 이래저래 핑계아닌 핑계로 미루고 미루다 급하게 풀었다!

[프로그래머스 level2] 소수 찾기

문제

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

접근 방법

완전 탐색인 문제이니까 어떻게 효과적으로 모든 경우를 체크할까 고민을 했다.
하지만 테스트 수를 보니까 상당히 작았다..!
-찌릿-
이건 순열 조합 써도 되겠다...!!
항상 순열 조합을 쓰고싶어 안달이 났었기에...!

그래서 순열을 통해 모든 나올 수 있는 수를 다 담고 set을 통해 중복의 수를 제거했다.
이후 for문을 통해서 소수를 판독하였다.

소수를 판독하는 알고리즘은 전에 과제로 좋은 효율을 내는 소수 판독 함수를 만들어서 적용했다.

풀이

from itertools import permutations


def isPrimeNumber(num):
    if (num <= 1):
        return False
    divisor = 2
    while (divisor < int((num ** 0.5) + 1)):
        if num % divisor == 0:
            return False
        divisor += 1
    return True


def solution(numbers):
    numbers = [i for i in numbers]

    answer = 0
    perNums = []
    setNums = []

    for i in range(1, len(numbers) + 1):
        perNums.append(list(permutations(numbers, i)))

    for i in perNums:
        for j in i:
            temp = ""
            for k in j:
                temp += k
            setNums.append(int(temp))

    setNums = set(setNums)

    for i in setNums:
        if isPrimeNumber(i):
            answer += 1

    return answer

좋은 웹페이지 즐겨찾기