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

문제 설명

프로그래머스 레벨2의 문제입니다. 순열을 이용하여 해결했습니다.

 

 

숫자로 이루어진 문자열이 주어졌을 때 각 숫자들로 만들 수 있는 수 중 소수를 찾는 문제입니다.

 

 

위와 같이 "17" 일 경우 1과 7로 만들 수 있는 숫자인 1, 7, 17, 71중 소수를 찾는 것 입니다. 7, 17 ,71이 소수이기 때문에 3이 반환되어야 합니다.

 

풀이

from itertools import permutations


def is_prime_num(n):
    if n == 0 or n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    i = 3
    while True:
        if i * i > n:
            break

        if n % i == 0:
            return False

        i += 1

    return True


def solution(numbers: str):
    str_nums_arr = []
    for n in numbers:
        str_nums_arr.append(n)

    nums_perm = []
    for i in range(1, len(str_nums_arr) + 1):
        nums_perm.extend(list(permutations(str_nums_arr, i)))

    int_nums_perm = []
    for item in nums_perm:
        int_nums_perm.append(int(''.join(item)))

    int_nums_perm = list(set(int_nums_perm))

    cnt = 0
    for n in int_nums_perm:
        if is_prime_num(n):
            cnt += 1

    return cnt

 

변수 설명

is_prime_num(n): 소수 인지 판별하는 함수입니다.

str_nums_arr: 문자열을 각각의 숫자 문자열로 변환된 값을 담는 배열입니다

nums_perm: 각 숫자들을 통해 만들 수 있는 순열입니다.

int_nums_perm: 순열을 int로 변환한 후 중복된 수를 제거한 배열입니다.

cnt: 총 소수의 수를 count하는 변수입니다.

 

간단 설명

먼저 이 문제는 순열을 통해 해결 했습니다. 순열이 헷갈리시는 분은 아래 글을 통해 직접 구현 또는 파이썬 내장 모듈을 통해 구하는 방법을 알 수 있습니다.

 

[알고리즘] 조합, 순열 알고리즘 (파이썬)

각 문자열로 만들 수 있는 모든 수를 구한 후 정수로 변환하여 중복을 제거해줍니다.

이때 순열을 구할때 1자리, 2자리, 3자리 ... (numbers의 길이) 까지 구해주기위해 for문으로 순회해줍니다.

 

그 후 각 문자열을 정수로 변환해 주기 위해 한번 더 순회하고 마지막 순회에서 소수라면 cnt의 값을 추가합니다.

 

이때 소수를 구하는 방법은 많은 문서가 있습니다. 저는 n이 0 또는 1이라면 소수 아님, 2라면 소수, 2로 나누어 떨어진다면 소수 아님으로 가장 먼저 한번 걸러주고 while문을 통해 sqrt(n)만큼 반복합니다. (i * i > n 일때 break) 만약 i로 나누어 떨어진다며 소수 아님, 그렇지 않다면 소수로 판별했습니다.

 

소수인지 판별하는게 중요한 문제가 아니므로 더 자세한 내용은 다루지 않도록 하겠습니다.