사용자 도구

사이트 도구


ps:problems:programmers:42839

소수 찾기

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42839
문제명소수 찾기
레벨Level 2
분류

소수 판별

시간복잡도O(n!*10^(n/2))
인풋사이즈n <= 7
사용한 언어Python
해결날짜2021/06/10
태그

고득점 Kit - 완전탐색

풀이

  • 그냥 무식하게 모든 가능한 숫자들을 다 만들어본다. itertools.permutation을 쓰면 간단하다. O(n!)개의 숫자들이 만들어진다.
  • 어떤 수 m이 소수인지 체크하는 것은 sqrt(m)까지로 다 나눠보면 되므로 O(sqrt(m))에 가능하다. m의 범위는 O(10^n)이다.
  • 결국 전체 시간 복잡도는 O(n!*10^(n/2)). 무시무시해보이지만 n≤7이라서 별 문제 없다.
  • O(n!)개의 수 중에서 중복되는 수를 한번만 카운트해야 하므로 set을 써서 중복을 제거하는 과정을 빼먹지 말것.

코드

"""Solution code for "Programmers 42839. 소수 찾기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42839
- Solution link: http://www.teferi.net/ps/problems/programmers/42839
"""

import itertools
import math


def is_prime(num):
    return (num >= 2 and
            all(num % i != 0 for i in range(2, math.isqrt(num) + 1)))


def solution(numbers):
    nums = set()
    for i in range(1, len(numbers) + 1):
        nums.update(int(''.join(x)) for x in itertools.permutations(numbers, i))
    return sum(1 for num in nums if is_prime(num))

토론

댓글을 입력하세요:
F G N G C
 
ps/problems/programmers/42839.txt · 마지막으로 수정됨: 2021/10/15 02:47 저자 teferi