[프로그래머스] 소수 찾기 (python)

 문제설명

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42839

---

Idea

1. 순열을 통해 조합할 수 있는 모든 경우의 수 탐색
2. 중복된 수 제거
3. 소수 여부 판별

---

Solution

from itertools import permutations

def isprime(n):
    flag = False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            flag = True
            break
    return True if not flag else False

def solution(numbers):
    # 0.09262283575
    p_list = list(set(int(''.join(p)) for i in range(1, len(numbers)+1) for p in permutations(numbers, i)))
    p_list = [p for p in p_list if p > 1]
    return len([p for p in p_list if isprime(p)])

입력된 numbers로 표현할 수 있는 모든 경우의 수를 계산하고 중복을 제거한 배열(p_list)을 생성합니다.

소수는 2부터 시작하기 때문에 0이나 1인 값을 제거합니다.

소수를 판단하는 함수(isprime)를 만들어 p_list에 있는 값이 소수인지 아닌지 판별합니다.

소수 판별은 2부터 √n까지의 값을 n이랑 나눠 0으로 나눠떨어지는지 판단합니다. 

나눠떨어지는 구간(n%i == 0)이 있다면 소수가 아니기 때문에 포문을 멈추고 소수가 아니라고 판단합니다.

※ √n까지 판별하는 이유는 여기를 참고해주세요.

import timeit
tests = ['11',
         '17',
         '011',
         '4444']
avg = 0.
for t in tests:
    avg += timeit.timeit(lambda: solution(t), number=10000)
print(avg / len(tests))

제가 푼 방식은 대략 0.092초 정도 걸리는 것으로 파악되었습니다.

---

Refactoring

def solution(numbers):
    # 0.092870956
    p_set = set(int(''.join(p)) for i in range(1, len(numbers)+1) for p in permutations(numbers, i))
    p_set -= set(range(0, 2))
    return len([p for p in p_set if isprime(p)])

입력된 numbers로 표현할 수 있는 모든 경우의 수를 계산하고 중복을 제거한 배열(p_list, set타입)을 생성합니다.

set은 차집합(-), 합집합(+)을 지원하기 때문에 이 기능을 활용하여 0과 1을 삭제합니다. (0, 1은 소수가 아님)

이후 동일하게 소수 여부를 판단합니다.

import timeit
tests = ['11',
         '17',
         '011',
         '4444']
avg = 0.
for t in tests:
    avg += timeit.timeit(lambda: solution(t), number=10000)
print(avg / len(tests))

Solution과 처리 속도는 거의 동일하지만 set을 이용한 풀이 방법을 공유하고자 refactoring에 기재하였습니다.

전체 코드는 아래 깃허브에서 확인 가능합니다.

https://github.com/daewoonglee/programmers/blob/master/lev2/%EC%86%8C%EC%88%98%20%EC%B0%BE%EA%B8%B0.py