[프로그래머스]소수 찾기

에라토스테네스체 개념을 되짚어 보고, 문제 조건을 세심히 읽어야할 필요성을 일깨워준 문제이다.

그리고, 지스트 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에 담아 중복을 제거한다.
-> 추출된 숫자를 기준으로 소수인지 여부를 에라토스테네스체의 배열로 확인한다.