프로그래머스 소수찾기 (Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/42839
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

틀린 코드

from itertools import permutations

def solution(numbers):
    answer = 0
    tmp = []
    for i in range(1,len(numbers)+1):
        if i == 1:
            for j in range(len(numbers)):
                tmp.append(numbers[j])
        else:
            tmp_li = list(permutations(numbers,i))
            for j in range(len(tmp_li)):
                tmp_word = ''
                for k in range(len(tmp_li[j])):
                    tmp_word += tmp_li[j][k]
                tmp.append(tmp_word)
    tmp = list(set(map(int, tmp)))
    print(tmp)
    for i in range(len(tmp)):
        flag = False
        if tmp[i] == 1 or tmp[i] == 0:
            continue
        for j in range(2,tmp[i]//2):
            if tmp[i] % j == 0:
                flag = True
        if not flag:
            answer += 1
            
                      
    return answer

이 풀이는 1개 틀리고 2개 시간초과가 난 코드이다.
일단을 풀려고하다보니 for문을 너무 많이 써서 시간초과가 난것같았다.
그래서 시간초과부터 잡기위해 다른 코드를 보며 공부를 했다.

맞춘 코드

from itertools import permutations
import math
def solution(numbers):
    answer = set()
    
    for i in range(1,len(numbers)+1):
        tmp_list = list(map(''.join,list(permutations(numbers,i))))
        tmp_list = list(set(map(int, tmp_list)))
        print(tmp_list)
        for i in range(len(tmp_list)):
            flag = False
            if tmp_list[i] < 2:
                continue
            for j in range(2,int(math.sqrt(tmp_list[i]))+1):
                if tmp_list[i] % j == 0:
                    flag = True
            if not flag:
                answer.add(tmp_list[i])

                      
    return len(answer)

이렇게 풀어서 성공했다.
차이점은 윗 풀이는 3중 for문 + 2중 for문으로 풀었는데
정리해서 3중 for문 한번으로 풀어버렸다.
''.join을 한번 씀으로써 장황했던 첫 3중for문을 해결 할 수 있었다!

이 방법을 쓰면서 두번째는 answer에 모든 경우의 수를 다 넣은 다음 set()로 중복 제거한거!

세번째는 내가 항상 소수판별할 때 시간초과가 났던 부분이다.
바로 대상 수(n)를 어디까지 나눠줘야하는 것인가? 에 관한것이다.
항상 범위를 2~n 혹은 2~n//2 까지 생각했다. 2가 나눌 수 있는 가장 작은 수 이니까!
근데 제곱근까지만 판별하면 더 적은 수를 가지고 소수를 판별할 수 있었다!!
n = X * Y 라고 생각하고 계산하는 방법을 생각해보니 이해가 쉬웠다.
참고자료 : https://makedotworld.tistory.com/13

p.s 에라토스테네스의 체의 방법을 사용하는 방법도 봤다. 하나의 체크리스트를 만들어서 하더라!! 아무래도 검사를 해놓으면 시간이 더 줄어들 것 같았다! 다음에 도전해봐야지~