소수찾기 -프로그래머스 완전탐색-

문제 설명

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

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

제한사항

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

입출력 예

numbers	return
17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

풀이

---

리스트의 숫자로 만들 수 있는 수를 만든 다음 소수인지 확인하여 소수일 때만 answer 값을 늘려주는 방식으로

문제를 풀기로 하였다 

 

소수를 판별하는 함수

def primenumber(n):
    if n !=1 and n!=0:
        for i in range(2,n):
            if n % i == 0:
                return False
            else:
                continue
    else:
        return False
    return True
    

 

0,1은 무조건 소수가 아니라고 판단하고 2부터는 자기자신을 제외하고 나눠지는 수가 있는지 확인하였다  

 

첫 번째 풀이(실패)

def solution(numbers):
    answer = 0
    numberlist = list(numbers)
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            if i != j:
                numberlist.append(numberlist[i]+numberlist[j])
            else:
                continue
    for i in range(len(numberlist)):
        if primenumber(int(numberlist[i])):
            answer +=1
        else:
            continue
    return answer

 

만들어지는 수를 위하여 numbers를 리스트로 만들어준 다음 합쳐줬는데 

저렇게 하면 1,2,3이 213이 되는 경우를 만들수 없었다

찾아보니 itertools를 import시켜서permutations를 사용하면 되는 것을 알게 되었다 

 

두 번째 풀이

import itertools
def solution(numbers):
    answer = 0
    numberlist=[]
    for i in range(1,len(numbers)+1):
        number = list(itertools.permutations(numbers,i)) 
        for j in number:
            number = "".join(j)
            numberlist.append(int(number))#처음에 int로 안만들어주고 구했으나 그렇게 하면 011과 11을 다르게 판단하여 중복으로 구하여서 int로 저장해주었다
    numberlist=list(set(numberlist))#중복을 지우기 위해 set을 한다음 다시 리스트로 만들어주었다 순서는 상관없기 때문에 사용할수 있던 방법
    for i in range(len(numberlist)):
        if primenumber(numberlist[i]):
            answer +=1
        else:
            continue
    return answer

 

처음에 int로 안 만들어주고 구했으나 그렇게 하면 011과 11을 다르게 판단하여 중복으로 구하여서 int로 저장해주었다

중복을 지우기 위해 set을 한 다음 다시 리스트로 만들어주었다 순서는 상관없기 때문에 사용 가능한 방법이었다

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges