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