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

문제

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

풀이

from itertools import permutations
def isPrime(n: int) -> bool:
    if n < 2 :
        return False
    for i in range(2, n) :
        if n%i == 0 :
            return False
    return True

def solution(numbers):
    num = list(numbers)
    p = num
    for i in range(2, len(numbers)+1) :
        p = p + list(map("".join, permutations(num, i)))
    
    answer = 0
    for v in p :
        if isPrime(int(v)) :
            answer += 1
    
    return answer

최초 시도. 중복되는 숫자를 잡아내지 못해서 틀렸다.
set을 이용해서 다시 해보자.

from itertools import permutations
def isPrime(n: int) -> bool:
    if n < 2 :
        return False
    for i in range(2, n) :
        if n%i == 0 :
            return False
    return True

def solution(numbers):
    num = list(numbers)
    p = num
    for i in range(2, len(numbers)+1) :
        p = p + list(map(int, map("".join, permutations(num, i))))
    
    answer = 0
    for v in set(p) :
        if isPrime(int(v)) :
            answer += 1
    
    return answer

테스트케이스 2, 4, 10, 12 에 걸린다.
정확한 이유는 모르겠지만… 아무래도

for i in range(2, len(numbers)+1) :
        p = p + list(map(int, map("".join, permutations(num, i))))

이 부분에서 p에 불필요한 덧셈이 진행되는 것 같았다.
어떡하지… 하다가 set을 마지막 정답 제출에만 사용해보기로 했다.

from itertools import permutations
def isPrime(n: int) -> bool:
    if n < 2 :
        return False
    
    for i in range(2, n) :
        if n%i == 0 :
            return False
        
    return True

def solution(numbers):
    answer = []
    for i in range(1, len(numbers)+1) :
        p = list(map(int, map("".join, permutations(numbers, i))))
        
        for v in p :
            if isPrime(int(v)) :
                answer.append(v)
    
    return len(set(answer))

이전 코드보다 반복문이 몇 차례 더 돌긴 할테지만, 잘 돌아간다.

테스트 1 〉	통과 (0.46ms, 10.3MB)
테스트 2 〉	통과 (150.29ms, 10.4MB)
테스트 3 〉	통과 (0.03ms, 10.4MB)
테스트 4 〉	통과 (141.59ms, 10.4MB)
테스트 5 〉	통과 (8.78ms, 10.6MB)
테스트 6 〉	통과 (0.03ms, 10.3MB)
테스트 7 〉	통과 (0.45ms, 10.3MB)
테스트 8 〉	통과 (9.63ms, 10.5MB)
테스트 9 〉	통과 (0.05ms, 10.4MB)
테스트 10 〉	통과 (2259.83ms, 10.4MB)
테스트 11 〉	통과 (74.85ms, 10.4MB)
테스트 12 〉	통과 (1.65ms, 10.4MB)

10번 케이스가 살짝 위험하긴 했는데, 통과했나보다.

더 나은 풀이

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

에라토스테네스의 체를 구현한 코드.
에라토스테네스 체 구현 엄두가 안났는데,
너무 쉽게들 성공하는구나.

테스트 1 〉	통과 (0.81ms, 10.5MB)
테스트 2 〉	통과 (71.06ms, 44.4MB)
테스트 3 〉	통과 (0.04ms, 10.4MB)
테스트 4 〉	통과 (50.34ms, 20MB)
테스트 5 〉	통과 (252.29ms, 145MB)
테스트 6 〉	통과 (0.04ms, 10.4MB)
테스트 7 〉	통과 (0.94ms, 10.5MB)
테스트 8 〉	통과 (682.53ms, 280MB)
테스트 9 〉	통과 (0.08ms, 10.4MB)
테스트 10 〉	통과 (327.74ms, 51.2MB)
테스트 11 〉	통과 (24.44ms, 13.8MB)
테스트 12 〉	통과 (5.43ms, 13.3MB)

내 코드가 더 빠른 케이스도 있고,
에라토스테네스 체 코드가 더 빠른 케이스도 있었다.
아마 input 값이 길수록 에라토스테네스가 빛을 발하는거겠지.