알고리즘 코드카타 104 - 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

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

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

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

numbers	return
'17'	3
'011'	2

 

처음에는 모든순열을 생성해서 그 원소들이 소수인지 아닌지 판별하려고 했는데 0의 예외처리가 상당히 곤란했다...

0이 하나일때는 단순하게 맨앞의 0을 지워주기만 하면 되었는데 0이 두개일때 세개일때를 고려하려니 상당히 복잡해졌다.

한참을 고민했는데 해결법은 의외로 단순했다. 순열을 생성하는 시점에서 정수형으로 바꿔서 입력하면 간단하게 맨 앞의 0이 삭제된다... 생각해보면 종종 당장의 해결책에 매몰되어서 간단한 방법을 떠올리지 못할때가 종종있는데 지금이 딱 그런 경우인것같다.

 

def solution(numbers):
    perms = []
    
    for i in range(1, len(numbers)+1):
        current_perms = itertools.permutations(numbers, i)
        perms.extend([int(''.join(map(str, perm))) for perm in current_perms])
    
    perms = list(set(perms))
    
    print(perms)

 

 

numbers의 순열을 생성하고 그것을 join한 후에 정수로 바꿔서 perms에 입력한다. 그리고 중복값을 제거하도록 했다.

이제 numbers로 만들 수 있는 모든 조합을 얻게 되었다. 나머지는 간단하다. perms의 원소들이 소수인지 아닌지 판정하기만 하면 된다.

def id_prime(n):
    if n <= 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    sqrt_n = int(n**0.5)
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

for perm in perms: # 소수여부 판정
        if id_prime(perm):
            answer += 1

 

이전에 작성해둔 소수 판별 함수를 불러온 후에  perms의 소수의 갯수를 세면 완료!

def solution(numbers):
    perms = []
    answer = 0
    
    for i in range(1, len(numbers)+1): # numbers로 만들 수 있는 모든 정수 조합을 생성
        current_perms = itertools.permutations(numbers, i)
        perms.extend([int(''.join(map(str, perm))) for perm in current_perms])
    
    perms = list(set(perms)) # 중복값 제거
    
    for perm in perms: # 소수여부 판정
        if id_prime(perm):
            answer += 1

    return answer

완료!

 

주어진 numbers의 길이가 짧아서 다행히 쉽게 풀 수 있었다.