소수 찾기 - 프로그래머스 - 파이썬 풀이

문제 풀이

문제 자체는 매우 간단합니다.

예시도 두 가지로 직관적입니다.

하지만 숫자 길이가 길어지면 시간 초과가 날 확률이 높습니다.

따라서 문제를 잘 이해하고 최적화할 부분을 찾는게 중요합니다.

풀이 과정

1. 소수가 될만한 후보를 찾습니다.
   1. 완전 탐색이 여기서 쓰입니다.
      1. permutations
2. 이 후보가 소수인지 확인합니다.
   1. 이 부분을 최적화해야 합니다!!
   2. 소수인지 판별하는 다양한 알고리즘을 구현해 이 부분만 수정합니다.
   3. 이런 기본적인 함수는 인터넷에 최적화 되어있는 코드가 많이 있습니다. 검색해서 활용합시다!

클린 코드 작성법

1. 변수명을 고쳐 문제의 이해력을 높입니다.
   1. number_string
2. 문제의 단계별로 함수화합니다.
   1. get_candidates
   2. check_prime
3. 문제를 풀어나갈 때, 과정을 잘게 쪼개면 최적화하기 쉽습니다.
   1. 오래 걸리면서 반복적으로 쓰이는 check_prime 함수만 최적화하면 됐습니다.

해답 코드

from itertools import permutations
import math 

def solution(numbers):
    number_string = numbers
    number_list = []
    for string in number_string:
        number_list.append(int(string))

    candidates = get_candidates(number_list)
    prime_count = 0
    for candidate in candidates:
        is_prime = check_prime(candidate)
        if is_prime:
            prime_count += 1
    return prime_count

def get_candidates(number_list):
    candidates = []
    length = len(number_list)
    for r in range(1, length + 1):
        candidates += permutations(number_list, r)

    final_candidates = set([])
    for candidate in candidates:
        transformed = tuple_to_int(candidate)
        final_candidates.add(transformed)
    return final_candidates

def tuple_to_int(tuple_):
    result = 0
    digit = 1
    for integer in tuple_:
        result += integer*digit
        digit *= 10
    return result

def check_prime(number):
    if number <= 1:
        return False
    if number % 2 == 0 and number > 2: 
        return False
    return all(number % i for i in range(3, int(math.sqrt(number)) + 1, 2))

도움이 됐다면 공감버튼을 눌러주세요! 질문이 있다면 댓글 달아주세요!

 

문제 링크

코딩테스트 연습 - 소수 찾기 | 프로그래머스