[프로그래머스]level2-소수 찾기-Python[파이썬]

문제링크

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

문제설명

알고리즘

ex) "011"
(1) 1개뽑아서 만들 수 있는 숫자
(2) 2개 뽑아서 만들 수 있는 숫자
(3) 3개 뽑아서 만들 수 있는 숫자
itertools의 permutations 함수를 이용하여 위 세개를 구할 수 있다.
pm(numbers, i) : numbers에서 i개 뽑아서 만들 수 있는 모든 경우의 수를 반환함.
ex) pm("011", 2)
--> 결과는 다음과 같이 튜플 형식으로 나옴
('0', '1')
('0', '1')
('1', '0')
('1', '1')
('1', '0')
('1', '1')
이를 join함수를 사용하여 숫자를 묶어주고 int를 씌어 정수로 만들어준다.
i = 1부터 numbers의 길이까지 pm함수에 대입하여 모든 경우의 수를 구한다.
그리고 이렇게 만든 정수들을 담는 set인 pm_results를 만든다.
pm_results의 결과는 다음과 같다.
{0, 1, 101, 10, 11, 110}
이 숫자들 중에 소수를 어떻게 찾을 수 있을까?
먼저 0, 1은 소수가 아니므로 집합의 차집합 연산을 이용하여 빼준다.
pm_results -= {0, 1}
그리고 2의배수, 3의배수, ... ($\sqrt{110}$ + 1)의 배수를 빼준다. (왜 최댓값의 루트를 씌운 값까지의 배수를 빼는지는 검색하면 나올것이다 ..^^)

    for i in range(2, int(max_num**(1/2)) + 1): # i의 배수들 제거하기
        temp_s = {i * j for j in range(2, max_num//i + 1)}
        pm_results -= temp_s

위 과정을 거친 후 마지막으로 남은 pm_results의 개수가 이 문제의 정답이 된다.

코드

from itertools import permutations as pm
def solution(numbers):
    pm_results = set()
    for i in range(1, len(numbers) + 1):
        i_result = pm(numbers, i) # numbers에서 i개 뽑은 결과
        for r in i_result:
            pm_results.add(int(''.join(r)))
    # 최댓값 범위 내에서 소수 찾기
    max_num = max(pm_results)
    for i in range(2, int(max_num**(1/2)) + 1): # i의 배수들 제거하기
        temp_s = {i * j for j in range(2, max_num//i + 1)}
        pm_results -= temp_s
        pm_results -= {0, 1} # 0과 1은 소수가 아니므로 제거한다.
    return len(pm_results)