08.14. 프로그래머스 : 소수 찾기 (LV.2) 완전탐색

🔎 소수 찾기

문자열로 주어진 숫자를 붙여서 소수를 몇개 만들 수 있는지를 구하라.

"""
1. 붙어있는 문자를 다 떼어놓기
2. 떼어놓은 문자들을 조합하여 숫자를 만들기
3. 숫자들의 소수를 판별하기
"""

💡 문제풀이#1

이 풀이의 핵심은 문자열 n의 길이(len)가 1일 때, 2일 때를 미리 생각해주는 것이었다.

import itertools

def prime(n):
    if n == 0 or n == 1:
        return False
    else:
        is_prime = int(n ** 0.5)
        for i in range(2, is_prime + 1):
            if n % i == 0:
                return False
        return True

def solution(numbers):
    answer = 0
    combi = []
    combination = []
    set_list = []

    for i in numbers:
        combi.append(i)
    
    if len(numbers) == 1 :
        if prime(int(numbers[0])) == True:
            answer += 1
            
    elif len(numbers) == 2:
        combination.append(int(numbers[0]))
        combination.append(int(numbers[1]))
        combination.append(int(numbers[0]+numbers[1]))
        combination.append(int(numbers[1]+numbers[0]))
        combination = list(set(combination))
        for n in combination:
            if prime(n) == True:
                answer += 1
        
    else:
        for i in range(2, len(numbers)+1):
            itertools_list = list(itertools.permutations(combi, i))
            for il in itertools_list:
                combination.append(il)
            
        for i in range(len(numbers)):
            combination.append(numbers[i])
        
        for i in combination:
            set_list.append(int(''.join(i)))
            set_list2 = list(set(set_list))
        
        for n in set_list2:
            if prime(n) == True:
                answer += 1

    return answer

 

처참하지만... 성공한게 어디야!

💡 문제풀이#2

그런데.. 길이를 고려할 필요가 없었다.
이미  우리가 구현한 함수 안에서 1인 경우와 2인 경우가 고려되고 있었기 때문이다.

def prime(n):
    # 1은 여기서 해결된다.
    if n == 0 or n == 1:
        return False
    else:
        is_prime = int(n ** 0.5)
        for i in range(2, is_prime + 1):
            if n % i == 0:
                return False
        return True

def solution(numbers):
    answer = 0
    combi = []
    combination = []
    set_list = []

    for i in numbers:
        combi.append(i)
    
    # if len(numbers) == 1 :
    #     if prime(int(numbers[0])) == True:
    #         answer += 1
            
    # elif len(numbers) == 2:
    #     combination.append(int(numbers[0]))
    #     combination.append(int(numbers[1]))
    #     combination.append(int(numbers[0]+numbers[1]))
    #     combination.append(int(numbers[1]+numbers[0]))
    #     combination = list(set(combination))
    #     for n in combination:
    #         if prime(n) == True:
    #             answer += 1
        
    # else:
    # 여기서 2는 해결된다.
    for i in range(2, len(numbers)+1):
        itertools_list = list(itertools.permutations(combi, i))
        for il in itertools_list:
            combination.append(il)

    for i in range(len(numbers)):
        combination.append(numbers[i])

    for i in combination:
        set_list.append(int(''.join(i)))
        set_list2 = list(set(set_list))

    for n in set_list2:
        if prime(n) == True:
            answer += 1

    return answer

# 테스트 5 : 통과 (2258.54ms, 12.2MB)

💡 문제풀이#3

생각보다 중복된 함수가 많아 보여서 중복을 줄여보았다. 
시간이 폭발적으로 줄어들었다. ( 2258.54ms > 12.69ms)

import itertools 

def is_prime(n):
    if n in [0, 1]:
        return False
    else:
        prime = int(n ** 0.5)
        for i in range(2, prime + 1):
            if n % i == 0:
                return False
        return True

def solution(numbers):
    answer = 0
    combi = [i for i in numbers]
    combination = []

    for i in range(1, len(numbers)+1):
        itertools_list = list(itertools.permutations(combi, i))
        for il in itertools_list:
            combination.append(int(''.join(il)))
            combination = list(set(combination))

    for n in combination:
        if is_prime(n) == True:
            answer += 1

    return answer

import itertools 

def is_prime(n):
    if n in [0, 1]:
        return False
    else:
        prime = int(n ** 0.5)
        for i in range(2, prime + 1):
            if n % i == 0:
                return False
        return True

def solution(numbers):
    answer = 0
    # combi for 문을 변경 후 삭제하였다.
    # for i in numbers:
    #   combi.append(i)
    combi = [i for i in numbers]
    combination = []
    # set_list = []
    # set_list = list(set()) 이렇게는 안된다..

    for i in range(1, len(numbers)+1):
        itertools_list = list(itertools.permutations(combi, i))
        for il in itertools_list:
            combination.append(int(''.join(il)))
            # set_list.append(int(''.join(il)))
            combination = list(set(combination))
            
    # 위 range를 1로 바꾸고 이 for문은 삭제. ('0',), ('1',), ('1',) 처럼 필요 없는 따옴표가 생겨서 분리하였었는데, 답안을 내는데는 아무런 문제가 없었다.
    # for i in range(len(numbers)):
    #     combination.append(numbers[i])

    # 위 함수에 합쳤다.
    # for i in combination:
    #     set_list.append(int(''.join(i)))
    #     set_list2 = list(set(set_list))

    for n in combination:
        if is_prime(n) == True:
            answer += 1

    return answer

# 테스트 5 : 통과 (12.69ms, 11.3MB)

💡 배운 점

1. from itertools import combinations : itertools 안에 많은 함수들이 내장되어 있기 때문에 필요한 부분만 import를 해서 쓰면 시간 측면에서 좋다. (프로그래머스에서는 이렇게 했더니 오류가 났다.. 왜지?)
2. 함수의 이름은 행동으로! prime 보다는 is_prime 이 좋다.
3. set_list = set() : set을 미리 상단에 선언해놓고 사용할 수 있다.
4. 변수로 할당했을 때 시간에서 유의미한 변화가 있었다. 이렇듯 파이썬의 최적화 방식을 따르면 자동적으로 네이밍 컨벤션까지 신경쓰게 되는 효과를 볼 수 있다. 최적화에 대해 많이 공부해보자.
(예시 : A += B 보다는 C = A + B, C를 불러오는 것이 효과적이다.)
5. if n == 0 or n == 1: 대신에 if num in [0, 1] 과 같이 쓸 수 있다.