[프로그래머스] 소수 찾기 문제풀이 python

🐒 문제

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

✍ 나의 풀이

import math
from itertools import permutations

def solution(numbers):
    answer = 0

    arr = [True]*10000000
    arr[0] = False
    arr[1] = False

    # 소수 9,999,999 까지 찾기
    for i in range(2, int(math.sqrt(10000000))):
        if arr[i]:
            j = 2
            while i*j <= 9999999:
                arr[i*j] = False
                j+=1

    nums = set()
    for i in range(1,len(numbers)+1):
        for j in list(permutations(numbers,i)):
            nums.add(int(''.join(j)))

    for i in nums:
        if arr[i]:
            answer += 1

    return answer

정확성  테스트
테스트 1 〉	통과 (3277.15ms, 86.1MB)
테스트 2 〉	통과 (3289.55ms, 86.8MB)
테스트 3 〉	통과 (3299.24ms, 86MB)
테스트 4 〉	통과 (3218.18ms, 86.5MB)
테스트 5 〉	통과 (3305.63ms, 87.2MB)
테스트 6 〉	통과 (3265.54ms, 85.9MB)
테스트 7 〉	통과 (3452.67ms, 85.9MB)
테스트 8 〉	통과 (3375.38ms, 87.4MB)
테스트 9 〉	통과 (3442.21ms, 85.9MB)
테스트 10 〉	통과 (3240.26ms, 86.5MB)
테스트 11 〉	통과 (3266.21ms, 86.4MB)
테스트 12 〉	통과 (3384.11ms, 86MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

완전탐색 카테고리의 문제를 풀었다.

---

🧠 문제 이해

소수판별

많은 수들의 소수 판별을 그때마다 하면 시간이 많이 소요될 것으로 예상되어,
미리 모든 수들의 소수 판별을 끝내놓고, 그 수가 소수인지 확인만 하려고 한다.

나는 문제에서 다음 조건을 확인하였다.

numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.

따라서 0부터 9,999,999까지 소수판별을 미리 해놓기로 했다.

소수 판별을 빠르게 하기위해 에라토스테네스의 체 알고리즘을 이용했다.

순열

입력이 '3'이라면 구해야할 경우의 수는 한개

3

입력이 '31' 이라면 구해야할 경우의 수는 네개

1, 3, 13, 31

입력이 '312' 이라면 구해야할 경우의 수는 열한개

1, 2, 3, 12, 13, 21, 23, 31, 32, 312, 321 

모든 경우의 수를 고려해야 할 때 어떤 라이브러리를 효과적으로 사용할 수 있을까?

순열: 서로 다른 𝑛개에서 서로 다른 𝑟개를 선택하여 일렬로 나열하는 것

순열(permutations)은 itertools 내장 라이브러리를 통해 사용할 수있다.

from itertools import permutations

permutations(iterable, r)

permutations의 첫번째 인자는 iterable, 두번째인자는 정수r 일때
iterable에서 서로다른 r개의 요소를 뽑아서 가능한 모든경우를 나열한 permuations객체를 반환한다.

따라서 list()함수에 넣어서 배열로 만들어주는 과정이 필요하다.

까먹어서 검색하면서 풀었다. 더 공부해야겠다.

---

리팩토링

import math
from itertools import permutations

def solution1(numbers):
    answer = 0

    nums = set()
    for i in range(1,len(numbers)+1):
        for j in list(permutations(numbers,i)):
            nums.add(int(''.join(j)))

    numsmax = max(nums)

    arr = [True]*(numsmax+1)
    arr[0] = False
    arr[1] = False

    # 소수 9,999,999 까지 찾기
    for i in range(2, int(math.sqrt(numsmax)+1 )):
        if arr[i]:
            j = 2
            while i*j <= numsmax:
                arr[i*j] = False
                j+=1

    for i in nums:
        if arr[i]:
            answer += 1

    return answer

정확성  테스트
테스트 1 〉	통과 (0.60ms, 10.4MB)
테스트 2 〉	통과 (174.19ms, 15.4MB)
테스트 3 〉	통과 (0.03ms, 10.4MB)
테스트 4 〉	통과 (68.58ms, 12.6MB)
테스트 5 〉	통과 (1014.67ms, 36.6MB)
테스트 6 〉	통과 (0.03ms, 10.3MB)
테스트 7 〉	통과 (0.58ms, 10.5MB)
테스트 8 〉	통과 (1797.43ms, 53.2MB)
테스트 9 〉	통과 (0.07ms, 10.4MB)
테스트 10 〉	통과 (228.02ms, 18.1MB)
테스트 11 〉	통과 (27.46ms, 11.1MB)
테스트 12 〉	통과 (10.65ms, 10.5MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

9,999,999까지 소수판별을 하지말고

먼저 구해야할 숫자들의 경우의 수를 구한뒤, 그중에서 가장 큰 수까지만 소수판별을 해도 되기때문에 그에 맞게 코드를 수정했다.