에라토스테네스체 개념을 되짚어 보고, 문제 조건을 세심히 읽어야할 필요성을 일깨워준 문제이다.
그리고, 지스트 https://gist.github.com/ 라는 사이트를 알게 되었다. 코딩 테스트 볼때에 유용하게 관리할 수 있기 때문에 한번 해보려고 한다...!(언제할지는 모르겠지만 ^^)...
아무튼 나는 이 문제를 풀때 3가지 짚고 넘어가야할 부분이 있었다.
1. 에라토스테네스의 체
def eratosthenes():
prime[0] = prime[1] = False
for i in range(2, 10000001):
if prime[i] == True:
for j in range(2 * i, 10000001, i):
prime[j] = False개념을 다시 생각해보면, 0과 1은 소수가 아닌 수로 설정하고 2부터 검사한다. 2는 소수이고, 2의 배수는 무조건 소수가 아니기 때문에 루프를 돌면서 False로 설정해주는 것이다. 가장 작은수부터 검사하기 때문에, 이미 이후에 수 들은 모두 검사 됐다.
2. 인덱스를 확인하자
에라토스테네스 배열을 형성할때 최초에 1000001으로 했었다. 근데 숫자의 조건이 numbers는 길이 1 이상 7 이하인 문자열입니다. 있었기 때문에, 런타임 에러가 발생했다. 처음부터 숫자의 범위를 확인할 줄 알아야 한다.
그리고 런타임 에러가 발생하면 인덱스 관련되어서 잘못된게 없는지 반드시 확인하자!!
1. 풀이
from itertools import permutations
prime = [True] * (10000001)
def eratostenes():
prime[0] = prime[1] = False
for i in range(2, 10000001):
if prime[i] == True:
for j in range(2 * i, 10000001, i):
prime[j] = False
def solution(numbers):
eratostenes()
num_card = list(numbers)
pick_num = set()
cnt = 0
for N in range(1, len(numbers) + 1):
permutate_num = permutations(num_card, N)
for i in permutate_num:
pick_num.add(int(''.join(i)))
for k in pick_num:
if prime[k]:
cnt += 1
return cnt그렇게 어려운 문제는 아니었다.
-> 숫자 배열로부터 임의로 n개를 뽑아서 숫자문자열을 형성
-> 그것을 set에 담아 중복을 제거한다.
-> 추출된 숫자를 기준으로 소수인지 여부를 에라토스테네스체의 배열로 확인한다.
