[Python] 프로그래머스 소수찾기

Level 2

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

---

첫 시도

permutations 활용하여 일단 모든 경우의 수 구함

근데 이때 튜플 형태로 반환됨

permutations 하는 range (1, len(numbers, 1) 되어야 함.

비효율적으로 바꾼거같지만 일단 통과

from itertools import permutations
import math

def solution(numbers):
    cnt = 0
    perm = []
    
    for i in range(len(numbers) + 1):
        perm.append(list(permutations(numbers, i)))
    joined = [''.join(num) for inner in perm for num in inner]
    nums = [n.lstrip('0') for n in set(joined) if n != '' or n != '0']
    nums = [int(n) for n in set(nums) if n != '' and n != '1']
    for n in nums:
        check = False
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                check = True
                break
        if check == False:
            cnt += 1
            
    return cnt

두번째 시도

첫 코드에서 앞에 받아오는 부분만 수정

Set에서 특정 범위의 원소들 제거하는 코드

시간 좀 더 빨라짐

from itertools import permutations
import math

def solution(numbers):
    cnt = 0
    temp = []
    
    for i in range(1, len(numbers) + 1):
        temp += list(permutations(numbers, i))
    nums = set(list(int(''.join(t)) for t in temp))
    nums -= set(range(0, 2))

    for n in nums:
        check = False
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                check = True
                break
        if check == False:
            cnt += 1
            
    return cnt

세번째 시도

구글링 참고

에라토스테네스의 체 활용

 

[에라토스테네스의 체]

대량의 소수를 한꺼번에 판별할 때 사용하는 알고리즘.

범위 안의 모든 수를 탐색하며 소수인지 아닌지 판별

소수를 판별할 범위만큼 배열을 먼저 할당하고 인덱스의 해당 값을 넣어준다

 

1. 배열을 생성하여 값을 초기화

2. 2부터 시작하여 특정 수의 배수에 해당하는 숫자들은 모두 지운다. ( 그 특정 숫자는 제외한 배수를 삭제)

3. 이미 지워졌으면 패스

4. 남아있는 숫자들을 출력

 

시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다. 다만 메모리가 많이 필요함. 

 

근데 하고 보니 시간은 원래 내가 짠 코드가 훨씬 빠르다..뭐지

일단 이 개념 기억하기..!

from itertools import permutations

def solution(numbers):
    ans = set()
    for i in range(len(numbers)):
        ans |= set(map(int, map("".join, permutations(list(numbers), i + 1)))) # union 연산자 활용하여 집합 바로 생성
        ans -= set(range(0, 2)) # 0에서 2 사이의 원소 제거
    for i in range(2, int(max(ans) ** 0.5) + 1): # 제곱근 까지의 범위만 확인
        ans -= set(range(i * 2, max(ans) + 1, i)) # i의 2배수부터 시작하여 max 값까지의 배수를 모두 해당 집합에서 제거
    return len(ans)

 

---

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

프로그래머스