[프로그래머스- 소수 찾기][파이썬]-15일차

https://programmers.co.kr/learn/courses/30/lessons/42839

--시간 초과 코드

-- 정답 코드

---

key point: permutations, 소수 로직에서 제곱근으로 시간 초과 해결하기

 

1. permutations 로 모든 경우의 수 구하기

모든 경우의 수를 구하고 ''.join( )으로 깔끔하게 구하고, sum(data,[]) 로 2차원 -> 1차원으로 바꾸고,

각 요소들에 int로 바꿔줌 map을 이용해서!

 

2. 소수 로직

원래는 부르트포스로 2부터 target 숫자 -1 까지 탐색하는 로직을 사용했는데, 시간 초과가 났다

ex) 9

1 x 9 =9

3 x 3=9

9 x 1=9

 

9의 소수 => 1,3,9

9의 제곱근=3

만약 3까지 돌았는데도 나눠지지 않는다 -> 3을 넘어서도 나눠지는 수가 없을 것이다 로 판별

 

소수인 11을 예시로

11의 제곱근은 3.31 정도 되는데, 

2,3 이 11을 나누어떨어지게 못함 -> 제곱근보다 큰 수로도 나눌 수 없다 라는 로직이다