[프로그래머스] Lv.2 - 소수찾기 (Python)

 

 

 

 

 

programmers.co.kr/learn/courses/30/lessons/42839?language=python3

코딩테스트 연습 - 소수 찾기

 

 

Stpes

1. num : 입력받은 숫자 문자열을 하나씩 리스트로 변환합니다.

2. finder(x) : 소수 찾는 함수를 만들었습니다.
   2-1 소수는 2부터 이므로, x가 1보다 작거나 같으면, False 반환합니다.
   2-2 x가 1보다 크면, 2부터 x의 제곱근까지 나누어지는 수 없으면 True(소수)반환합니다.

3. 소수 개수 세기위한 count 리스트를 선언합니다.

4. 1개부터 위에서 선언한 num의 숫자 개수만큼 모든 조합의 수를 순열을 이용해 구합니다.

5. 순열 내의수를 join을 통해 결합 후 소수인지 판단합니다.

6. 조합한 수가 소수가 맞다면 count리스트에 추가합니다.

7. count 리스트에 추가 된 소수들을 set을 통해 중복을 지워주고 개수는 len함수를 사용하여 반환합니다.

 

[순수 코드]

from itertools import permutations
import math
def solution(numbers):
    
    num = [i for i in numbers]
    
    def finder(x):
        if x <= 1:
            return False
        else:
            for i in range(2, int(math.sqrt(x))+1):
                if x % i == 0:
                    return False
            return True
    
    count = []
    
    for i in range(1, len(num)+1):
        ans = set(list(permutations(num,i)))
        for j in ans:
            if finder(int(''.join(j))):
                count.append(int(''.join(j)))
                
    return len(set(count))

✨key✨

여기서 소수찾는 함수 만드는게 중요하다고 생각합니다.

처음에 제가 함수를 조금 복잡하게 만들었을때는 

시간초과로 실패를 했었습니다.

 

그리고 Lv1에서 풀었던 소수찾기 문제를 참고해서 

간단하게 함수를 다시 만들었고 

이를 통해 시간 복잡도 문제를 해결할 수 있었습니다! 

 

[Line 설명]

from itertools import permutations
import math
def solution(numbers):
    
    # 입력받은 숫자 문자열을 하나씩 리스트로 변환 
    num = [i for i in numbers]
    
    #소수 찾는 함수
    def finder(x):
        # 소수는 2부터 이므로, x가 1보다 작거나 같으면, False 반환
        if x <= 1:
            return False
        # x가 1보다 크면, 
        else:
            # 2부터 x의 제곱근까지 수 중 나누어지는 수가 있으면(소수가 아니면) False 반환
            for i in range(2, int(math.sqrt(x))+1):
                if x % i == 0:
                    return False
        # 2부터 x의 제곱근까지 나누어지는 수 없으면 True반환 (소수)
        return True
    
    #소수 개수 세기위한 count 리스트
    count = []
    
    # 1개부터 위에서 선언한 num의 숫자 개수만큼 모든 조합의 수를 순열을 이용해 구함
    for i in range(1, len(num)+1):
        ans = set(list(permutations(num,i)))
        
        # 순열 내의수를 join을 통해 결합 후 소수인지 판단합니다. 
        for j in ans:
            if finder(int(''.join(j))):
                #조합한 수가 소수가 맞다면 count리스트에 추가합니다.
                count.append(int(''.join(j)))
                
    #이렇게 count 리스트에 추가 된 소수들을 set을 통해 중복을 지워주고 개수는 len함수를 사용하여 반환합니다.
    return len(set(count))