소수 찾기

문제풀이

def prime_number(number):   # number를 입력 받아 소수인지 아닌지 구분하는 함수
     # number가 1이 아니면, (1은 소수가 아님)
    if number != 1 and number != 0:                 
        # 2, 3, 4, ..., (number - 1)까지의 인수에 대해서
        for f in range(2, number):  
            # number가 위의 인수 중의 하나로 나누어지면, (나머지가 0이면)
            if number % f == 0:     
                return False    # 소수가 아님
    else:                       # number가 1이라면, 
        return False            # 소수가 아님
    
    # number가 1이 아니면서, 2부터 (number - 1)까지의 수로 나눠지지 않으므로
    # 소수로 판별됨 (소수는 1과 자신만을 인수로 갖는 수)
    return True 

def make_num(number_list, numbers):
    
    all_numbers = []
    
    for maked_num in number_list:
        for last_num in numbers:
            new_number_list = number_list[:]
            new_numbers = numbers[:]
            new_num = maked_num + last_num
            new_number_list.append(new_num)
            new_numbers.remove(last_num)
            all_numbers.append(new_num)
            all_numbers += make_num(new_number_list, new_numbers)
    
    return all_numbers

def solution(numbers):
    answer = 0
    
    numbers = list(numbers)
    
    all_numbers = []
    
    for num in numbers:
        number_list = []
        new_numbers = numbers[:]
        new_numbers.remove(num)
        number_list.append(num)
        all_numbers.append(num)
        all_numbers += (make_num(number_list, new_numbers))
      
    all_numbers = set(all_numbers)
    all_numbers = list(all_numbers)
    
    for idx, num in enumerate(all_numbers):
        all_numbers[idx] = int(num)
    all_numbers = set(all_numbers)
    
    for num in all_numbers:
        if prime_number(num):
            answer += 1
    
    return answer

알고리즘

나는 재귀와 DFS를 사용했다.

DFS의 시작을 주어진 숫자들을 반복문안에서 하나씩 뽑아서 재귀 함수에[ 넣어 시작했다.

그러면 모든 경우의 수를 최종적으로 얻을 수 있었다.

 

후에 이 문제를 더 간단하게 풀 수 있도록 더 노력해야겠다. 지금의 코드는 너무 난잡하다.

출처

문제: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습