[스파르타] 99클럽 코테스터디 7일차 TIL / 소수 찾기

프로그래머스: 소수 찾기 (링크)

소수 찾기

 

소수 자체를 판별하는 방법은 예전에 풀어봐서 알고 있었는데 가능한 조합을 찾는 방법이 바로 떠오르지 않았다. permutations 사용은 감이 왔는데 매번 달라지는 가짓수를 어떻게 선택하나 싶었다가 다른 분의 블로그에서 힌트를 얻을 수 있었다. 그냥 for문 돌리면서 가짓수를 변경한 조합을 리스트에 저장하고 나중에 join으로 합쳐준 뒤 int로 변경하면 되는 방식이었다.

 

이렇게 되면 "17"이 주어졌을 때 int_num에는 [1, 7, 17, 71] 이 남게 된다. 그리고 하나 더 중요한 점이 combination이 아니라 permutation을 사용했기 때문에 만약 [1, 1, 2]인 경우 11이 2번 나오게 된다. 이런 경우 때문에 정답을 출력 시 set으로 중복을 제거하였다. 또한 prime_number 함수로 판별할 수 없는 0 또는 1도 사전에 answer 리스트에 들어갈 수 없게 방지해야 한다.

 

import math
from itertools import permutations

# 소수 판별
def prime_number(x):
    for i in range(2, int(math.sqrt(x) + 1)):	
    	if x % i == 0:		
        	return False
    return True
                    
def solution(numbers):
    numbers = list(numbers)
    str_num = []
    answer = []
    
    for i in range(1, len(numbers)+1):
        str_num += list(permutations(numbers, i))
        
    int_num = [int(''.join(num)) for num in str_num]
    
    for i in int_num:
        if i < 2:
            continue
            
        if prime_number(i):
            answer.append(i)
            
    return len(set(answer))

오늘 미들러 풀이 끝!

---

참고한 블로그: https://dev-note-97.tistory.com/99