[프로그래머스] 소수찾기 lvl.2 - PYTHON

'프로그래머스 - 소수찾기'

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

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

제한사항

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

입출력 예

numbers
"17"
"011"

return
3
2

👨‍💻 문제를 풀기위한 학습!

Permutation - 순열

---

리스트 안에 있는 값으로 만들 수 있는 모든 경우

[a, b, c]

a의 위치를  swapping
[a, b, c]	[b, a, c]	[c, b, a]
b의 위치를  swapping
[a, b, c]	[b, a, c]	[c, b, a]
[a, c, b]	[b, c, a]	[c, a, b]

example code

def perm(input, i):
    if i == len(input) - 1:
        print(input)
    else:
        for j in range(i, len(input)):
            input[i], input[j] = input[j], input[i]
            perm(input,i + 1)
            input[i], input[j] = input[j], input[i]
         
perm([a,b,c], 0)



[a, b, c]

a의 위치를  swapping
[a, b, c]	[b, a, c]	[c, b, a]
b의 위치를  swapping
[a, b, c]	[b, a, c]	[c, b, a]
[a, c, b]	[b, c, a]	[c, a, b]

permutation - 순열

from itertools import permutations

permutations([a,b,c])

permutations([a,b,c], len(arr)) 
#2 매게변수는 경우의 수의 배열 길이

✔ My Solution

---

from itertools import permutations

def solution(numbers):
    answer = 0                                 
    nums = [i for i in numbers]              
    permutatedL = []
    
#   순열 리스트 만들기
#   0개인 순열은 필요없음 1부터 시작
    for i in range(1, len(numbers)+1):            
        permutatedL += list(permutations(nums, i))  
    
#   순열로 받은 이상한 데이터
#   "".join()으로 문자열 변환 후 숫자로 변환
    arrP = [int(("").join(p)) for p in permutatedL]
#   set()의 mutable값 제거로 반복된 리스트 제거
    arrS = list(set(arrP))

#   소수찾기
    for num in arrS:                           
        if num >= 2:                                
            flag = True            
            for j in range(2,num):       
                if num % j == 0:                       
                    flag = False
                    break
            if flag:
                answer += 1
                

    return answer

​

step 1

    for i in range(1, len(numbers)+1):            
        permutatedL += list(permutations(nums, i))  

✅ 1 ~ i 자리수의 경우의 수 를 리스트화

step 2

    arrP = [int(("").join(p)) for p in permutatedL]
    arrS = list(set(arrP))

✅ set()의 mutable값 제거로 반복된 리스트 제거

step 3

#   소수찾기
    for num in arrS:                           
        if num >= 2:                                
            flag = True            
            for i in range(2,num - 1):       
                if num % i == 0:                       
                    flag = False
                    break
            if flag:
                answer += 1
                
    return answer   

✅ 소수 조건

• 2보다 크거나 같다
• num이 2와 num - 1 사이의 수와 나눠지면 flag = False 후 break
• 각 숫자의 소수 조건 반복문을 돌려 연산
• flag가 True 일 때 answer += 1
  
  
  
  

step 3 - 1

💪 improved method

#   소수찾기
    for num in arrS:                           
        if num >= 2:                                
            flag = True            
            for i in range(2,int(num ** 0.5) + 1):       
                if num % i == 0:                       
                    flag = False
                    break
            if flag:
                answer += 1
                
    return answer  

기존 for문이 2에서 num - 1 까지 돌았던 것을 2에서 num의 제곱근까지만 돌도록 처리해주어 연산 횟수를 절반에 가깝게 줄여줄 수 있다.