[프로그래머스 / 완전탐색 / Python] 소수 찾기

문제 설명

 

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

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

제한사항

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

 

입출력 예
numbers	return
"17"	3
"011"	2

 

 

---

풀이 코드

 

import itertools

def solution(numbers):
    
    lst = []
    answer = []
    for i in range(1,len(numbers)+1):
        lst += itertools.permutations(numbers, i)
    
    for j in lst:
        tmp = "".join(j)
        if tmp[0] != '0':
            answer.append(int(tmp))
            
            
    answer = list(set(answer))
    ans = []
    for k in answer: 
        cur = False
        for l in range(2,int(k**0.5)+1):
            if k%l == 0:
                cur = True
        if cur == False:
            ans.append(k)
        
    if 1 in ans:
        return len(ans)-1
    else:
        return len(ans)

 

 

---

풀이 과정

 

1. 조합 만들기

import itertools
 
 lst = []
 answer = []
 for i in range(1,len(numbers)+1):
 lst += itertools.permutations(numbers, i)

for j in lst:
	tmp = "".join(j)
	if tmp[0] != '0':
		answer.append(int(tmp))


answer = list(set(answer))

 

1) itertools의 permutations 함수를 이용해 만들 수 있는 모든 조합의 수를 만든 후 join을 이용하여 ('2','3') 이렇게 되어있는 원소들을 '23'으로 합치는 작업을 했다.

 

2) 이때, 문자열의 0번째 인덱스가 0인것은 정수형으로 바꿀 때 에러가 나기 때문에 이 경우를 제외한 문자열들만 정수형으로 바꿔 answer이라는 리스트에 넣어주었다.

 

3) 이후 set을 이용하여 중복제거를 해주었다.

 

 

2. 소수찾기

ans = []
    for k in answer: 
        cur = False
        for l in range(2,int(k**0.5)+1):
            if k%l == 0:
                cur = True
        if cur == False:
            ans.append(k)
        
    if 1 in ans:
        return len(ans)-1
    else:
        return len(ans)

 

1) 최종 답을 ans라는 리스트에 담기 위해 ans = [] 선언을 해주고, answer 리스트에서 소수인 수를 찾아 ans리스트에 넣어주었다.

 

2) 답의 형태는 소수의 갯수임으로 ans의 길이를 리턴해주면 된다. 허나 아까 1이 있는 경우 예외처리를 안해줬으므로 정답을 리턴할 때 1이 있는 경우 len(ans)에 -1 을 하여 리턴한다.

 

 

 

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

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

 

 

공간복잡도가.. 안좋은 코드이다..

 

 

 

---

다른 풀이 과정

 

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)