프로그래머스 소수찾기 (파이썬)

Level 2 완전탐색

 

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

코딩테스트 연습 - 소수 찾기

 

정답 코드

from itertools import permutations

def prime(num):
    sieve = [1] * (num + 1)
    MAX = int(num ** (0.5))
    for i in range(2, MAX + 1):
        # i 가 소수라면
        if sieve[i] == 1:
            # 배수는 모두 소수가 아니다
            for j in range(i + i, num+1, i):
                sieve[j] = 0
    return [i for i in range(2, num + 1) if sieve[i] == 1]

def solution(numbers):
    arr = list(numbers)
    arr.sort(reverse=True)
    num = int("".join(arr))
    primeList = prime(num)
    temp = []
    for i in range(1, len(arr) + 1):
        temp.append(list(set(permutations(arr, i))))
    permutation = []

    for i in range(len(temp)):
        for j in range(len(temp[i])):
            num = int("".join(temp[i][j]))
            if num >= 2 and num in primeList and num not in permutation:
                permutation.append(num)

    answer = len(permutation)
    return answer

소수를 판단하는 데 에라토스테네스 체를 이용해서 numbers의 가장 큰 값 이하의 소수를 모두 찾았주었습니다.

순열을 사용하면 시간복잡도가 N!이라서 시간초과가 발생하지 않을까 생각했는데 다행히 N의 최대가 7이라서 순열을 사용했습니다.

set과 permutation을 이용해서 중복되는 값을 배제시키고 소수를 모두 찾았습니다.

set은 그대로 사용하면 index로 접근이 안되어서 list로 바로 바꿔주었습니다.

 

좋아요를 가장 많이 받은 코드 

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)

저와 비슷하게 permutations를 사용했지만 map과 join을 적절하게 사용해서 코드를 간결하게 만든 것이 제 코드와의 큰 차이점이었습니다.

그리고 에라토스테네스 체 방법으로 소수를 구한 것은 맞지만 저는 n 이하의 모든 값을 먼저 찾아 소수인 것만 따로 모았다면 위 코드는 후보 중에서 소수가 아닌 것을 제거하는 방법으로 2줄 만으로 간결하게 코드를 구현한 것이 배울 점이라고 생각했습니다.