내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
소수 찾기
ps:problems:programmers:42839
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 소수 찾기 ====== ===== 풀이 ===== * 그냥 무식하게 모든 가능한 숫자들을 다 만들어본다. itertools.permutation을 쓰면 간단하다. O(n!)개의 숫자들이 만들어진다. * 어떤 수 m이 소수인지 체크하는 것은 sqrt(m)까지로 다 나눠보면 되므로 O(sqrt(m))에 가능하다. m의 범위는 O(10^n)이다. * 결국 전체 시간 복잡도는 O(n!*10^(n/2)). 무시무시해보이지만 n≤7이라서 별 문제 없다. * O(n!)개의 수 중에서 중복되는 수를 한번만 카운트해야 하므로 set을 써서 중복을 제거하는 과정을 빼먹지 말것. ===== 코드 ===== <dkpr py> """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)) </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_2}}
ps/problems/programmers/42839.txt
· 마지막으로 수정됨: 2021/10/15 02:47 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로