[프로그래머스] 소수 찾기- python[ Brute Force]

[level 2] 소수 찾기 - 42839

문제 링크

성능 요약

메모리: 10.2 MB, 시간: 0.65 ms

구분

코딩테스트 연습 > 완전탐색

채점결과

Empty

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

나의 풀이

1. 가진 숫자로 모든 경우를 조합하는 방법
2. 소수판별 알고리즘
2가지 로직이 필요한데, 2번이야 간단하게 2 ~ num/2인 경우랑 비교해서 나눠떨어지면 넘겨주고,
BruteForce로 조합가능한 리스트를 만들고 set 씌워서 중복처리 하는것도 괜찮을듯.

풀면서 이 방법이 맞는 풀이인가 굉장히 궁금해졌던 문제였다. 전체 순열을 구하는 방법이 잘 떠오르지 않아 예전에 짰던 코드를 사용하여 코드를 작성했다.

check 배열은 해당 값이 사용되었는지 기록하는 배열이고(arr = [1,2,3] , check = [1,0,1] 이면 현재 순열을 만드는데 1,3만 사용했다는 뜻임)

sel 배열은 현재 값이 저장되어 있는 배열이다.(depth가 length와 같아지면 sel안의 값을 추가해준다)

global cases,sel,check

def perm(depth,nums, length):  # 각자 뎁스에서는? 
    global check,sel,cases
    if depth == length:  # 최고 뎁스에 도달했으면? # if depth == len(sel)
        cases.append(int(''.join(sel)))
        return
    
    for i in range(length):  # 3번의 화살표 떨어트릴 기회
        if not check[i]:  # 각 기회 안에서 check를 보고 멈출 수 있는지 보고?
            check[i] = 1  # 멈출 수 있다면 if 통과했으니까 자리 차지했다고 표시하고
            sel[depth] = nums[i]  # 화살표가 떨어진 위치의 재료리스트
            perm(depth+1,nums,length)
            check[i] = 0  # 돌아나오면서 다시 다음을 위해 초기화!! (중요)


def isPrime(num):
    if num <2:
        return False
    for i in range(2,num//2+1):
        if num % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    global sel,check,cases
    cases = []
    #모든 경우 조합
    for i in range(len(numbers)):
        sel = [ '' for _ in range(len(numbers))]
        check = [ 0 for _ in range(len(numbers))]
        perm(i,numbers,len(numbers))
    #중복 제거
    cases = list(set(cases))
    #소수 판별
    for case in cases:
        if isPrime(case):
            answer+=1
    return answer

다른 사람의 풀이를 확인해보니 대부분 순열 조합을 사용한 것을 볼 수 있었다. 잘못된 풀이는 아니었다는 결론을 내릴 수 있었다. 

다만 순열 조합 코드 작성에 대한 숙련도가 아직 부족한듯하여 연습이 필요할듯함.