프로그래머스 고득점 Kit - 소수 찾기

 

Problem

https://school.programmers.co.kr/learn/courses/30/parts/12230

프로그래머스

• 한자리 숫자가 적힌 종이 조각이 흩어져 있다.
• 흩어진 종이 조각을 붙여 만들 수 있는 소수의 개수를 구해라
• 각 종이 조각에 적힌 숫자가 문자열로 주어질 때, 만들 수 있는 소수의 개수를 반환해라

Input / Output Example

numbers	return
"17"	3
"011"	2

 

Solution

일단 해당 코드가 완전탐색 카테고리에 있으니.. 단순 무식하게 모든 경우의 수를 다 구하는 방법으로 접근했다.

파이썬 itertools의 permutations(순열 생성 도구)를 통해 길이 1부터 len(numbers) 까지의 순열의 리스트를 구했다.

여기에서 set을 사용해서 중복을 제거해줬다.

 

소수를 판별할 때에는 에라토스테네스의 체를 이용했다.

1부터 N까지 범위 사이에서 소수를 구할때, 에라토스테네스의 체는 다음과 같다.

• 1부터 N까지 나열한다.
• 소수도, 합성수도 아닌 자연수 1을 제거한다.
• 2를 제외하고, 2의 배수를 제거한다.
• 3을 제외하고, 3의 배수를 제거한다.
• 4는 2의 배수를 제거하는 과정에서 지워졌다.
• 5를 제외하고, 5의 배수를 제거한다.
• 이 과정을 $\sqrt{n}$ 까지 반복한다.
• 남아있는 수 = 소수가 된다.

 

해당 문제를 풀 때는 기본값이 True인 bool 리스트를 만들어서 합성수면 False로 바꾸는 방법을 통해 소수를 구했다.

 

통과과 되긴 하지만, 거의 4초가 걸릴 정도로 효율적인 코드는 아닌 것 같다.

 

Code

from itertools import permutations

def solution(numbers):
    answer = 0
    set_num = set()
    max_num = 0
    # 만들 수 있는 모든 숫자 구하기
    for i in range(1, len(numbers)+1):
        nPr = permutations(numbers, i)
        for j in nPr:
            number = int(''.join(j))
            if number >= 2:
                set_num.add(number)
                if max_num < number:
                    max_num = number
	# 배열의 최댓값 기준으로 에라토스테네스 체
    erthos = [True] * (max_num+1)
    for i in range(2, int((max_num+1)**(1/2))):
        for j in range(2*i, max_num+1, i):
            erthos[j] = False
    
    for i in set_num:
        if erthos[i]:
            answer += 1
    
    return answer