프로그래머스 Lv2. 소수찾기 - Python

문제 링크

나의 풀이

# perm의 시간복잡도 : O(n!)
# comb의 시간복잡도 : O(nCr)

import math
from itertools import permutations

def solution(numbers):

    max = 10000000 # 에라토스테네스의 체를 이용해 소수 테이블 미리 생성
    array = [True for _ in range(max + 1)]
    for i in range(2, int(math.sqrt(max)) + 1):
        if array[i] == True:
            j = 2
            while j * i <= max:
                array[i * j] = False
                j += 1
    array[1] = False
    array[0] = False

    numlist = list(numbers)

    permlist = []
    for r in range(1, len(numlist) + 1):
        for perm in permutations(numlist, r):
            permlist.append(int(''.join(perm))) # perm은 ('1','7') -> ''.join(perm)하면 '17' -> int하면 17
    # permutation을 쓸 수 있는 근거는 n, r의 최대값이 7이기 때문에 O(n) * O(n!) 충분히 가능

    answer = 0
    permlist = list(set(permlist))
    # permlist에 중복 제거. 만약 0,1,1이 numlist라면 permutations는 '1' 두개를 다른 것 취급함. 그래서 011, 011이렇게 중복이 발생
    for p in permlist:
        if array[p] == True:
            answer += 1

    return answer

생각 과정

문제를 읽고 소수인지 아닌지는 에라토스테네스의 체를 이용해 판별하면 되겠다고 생각했다. 남은 문제는 numbers로 들어오는 문자열을 분리해서 가능한 모든 조합을 리스트로 만들고 이 리스트를 순회하며 소수 판별을 해야하는데, permutations이 제일 먼저 떠올랐다. 하지만 permutations의 시간복잡도는 O(n!)이기 때문에 항상 주어진 수의 범위를 확인하고 사용이 가능한지 확인해야한다. 이 문제에서는 n이 7이하 이기 때문에 for문을 순회하며 permutations(numlist, r)을 해도 시간복잡도가 O(n) * O(n!) 이라도 충분히 동작한다.

정리

1.  perm의 시간복잡도 : O(N!)
2.  permutations의 대상 원소에 중복된 값이 있으면 결과에도 중복된 값이 존재하게 됨.
    (0,1,1)에서 중복되는 1을 다른 것으로 보기 때문
3.  ''.join()은 iterable을 이어줌