문제
https://school.programmers.co.kr/learn/courses/30/lessons/42839
어려운 문제만 풀다보니 힘들어서.. 이번엔 좀 라이트한 문제로
주요 아이디어
- 소수 구하는 함수 따로 작성
- 주어진 문자열로 만들 수 있는 모든 숫자 조합 생성하기
- 가능한 소수 카운트!
코드 구현 (Python 3)
더보기
from itertools import permutations
def prime_num(x):
# 1, 자기자신 외 약수
# 약수 구하기
if x < 2:
return False
elif x == 2:
return True
else:
for i in range(2, x):
if x % i == 0:
return False
return True
def solution(numbers):
# 모든 조합
numbers = [x for x in numbers]
perm_list = []
answer = 0
for i in range(1, len(numbers)+1):
perm = permutations(numbers, i)
perm = [int(''.join(x)) for x in perm]
perm_list += perm
perm_list = list(set(perm_list))
for num in perm_list:
if prime_num(num) == True:
answer += 1
return answer
제출 결과
코드 개선 방안
이번에는 그냥 약수를 찾는 것으로 풀렸지만, 시간 조건이 빡빡한 경우에는 소수 찾기에서도 시간 초과가 걸리는 경우가 있어서 추가로 적어둔다.
에라토스테네스의 체
핵심은 n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n) 까지만 검사하게끔 range 범위를 좁혀주는 것이다.
def check_prime(num):
if num == 1: return False
else:
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 튜플 (0) | 2024.04.07 |
---|---|
[프로그래머스] 두 개 뽑아서 더하기 (0) | 2024.04.07 |
[프로그래머스] 순위 검색 (0) | 2024.04.07 |
[프로그래머스] 사칙연산 (0) | 2024.04.05 |
[프로그래머스] 퍼즐조각 채우기 (0) | 2024.04.02 |