[프로그래머스]소수 찾기(python)

요 며칠 동안 풀었던 알고리즘이 너무 어려워서

자신감 충전 겸 간단한 문제를 풀어보았다.

 

근데 더 자신감 없어졌ㅇ....

 

일단 이 문제는 소수에 관한 문제로 이전에 풀었던 소수 문제와 소수 시리즈로 묶어볼까 한다.

 

 

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

프로그래머스

문제 설명

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

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

 

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.

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

입출력 예시(기본 테스트 케이스)

Input(numbers)	Output(return)
"17"	3
"011"	2

 

문제는 간단하다. 

입력값으로 숫자 배열이 주어지는데 이걸 한 자리씩 잘라 다시 합쳐 여러 조합을 만들 수 있다. 

이렇게 만든 조합 중 소수의 개수를 찾아 return 하면 되는 문제이다. 

 

즉 뽑아서 합치는 숫자들의 순서가 중요하므로 순열 문제라고 판단할 수 있다. 

또는 bfs, dfs 같은 완전 탐색으로 모든 경우의 수도 구할 수 있다. 

하지만 파이썬은 순열 조합 라이브러리 사용이 쉬우므로 순열로 풀어보았다. 

 

이렇게 구해진 숫자들을 문자열을 통해 합치고 소수인지 판별하면 된다. 

 

여기서 주의해할 점은 문자열로 합쳐져 011과 11을 다른 값이라고 판단하는 부분이다. 

같은 값으로 분류를 위해 맨 앞자리에 0이 있는 경우 0을 빼는 부분과 중복 제거를 거쳐야한다.

 

소수 판별 알고리즘은 처음에는 예전에 풀었던 로직 그대로 썼다. 

 

~소수 시리즈~

1. [프로그래머스] 소수 만들기 

https://study-hub.tistory.com/9

[프로그래머스]소수 만들기 (python풀이)

 

그때는 테스트 케이스에 별다른 제약조건이 없어서 기본 소수의 정의대로

2부터 나누어가며 약수를 탐색하고 약수가 없으면 소수로 판단했다. 

 

하지만 이 문제는 그렇게 풀면 테스트 케이스에서 막힌다. (왜지)

 

사실 소수를 구할 때는 구하고 싶은 숫자의 제곱근까지의 수만 탐색하면 된다. 

왜냐하면 그 이전에 약수가 나왔다면 그 값이 제곱근 보다 큰 수의 약수일 것이기 때문이다. 

 

예를 들어 16의 제곱근은 4이다.

2, 4, 8, 16 이 약수이며 2, 4는 8, 16의 약수이기도 하다.

그러므로 16은 소수가 아니다. 

 

해당 내용을 적용하여 함수를 수정하면 모든 테스트 케이스가 통과된다. 

 

풀다가 에라토스테네스의 체로 푸는 풀이도 발견했는데 이건 다음번에... 소수 관련된 문제 나오면 적용해서 풀어볼까 한다. (세상에 문제는 많으니까)

 

from itertools import permutations
from collections import defaultdict
import math

#소수판별함수
def primNum(num):
    #입력이 0, 1이 아닐때
    if num == 1 or num == 0:
        return False
    for k in range(2, int(math.sqrt(num) + 1)): #2부터~ 제곱근의 올림까지
        if (num % k == 0): #나머지가 0이 아니여야 소수
            return False
            
    return True

def solution(numbers):
    answer = 0
    result =  defaultdict(list) 
    N = []
    
    for i in range(0, len(numbers)):
        result = list(permutations(numbers, i+1)) #순열구하기 (1개뽑기~n개뽑기)

        for j in range(0, len(result)): 
            num=''.join(result[j]) #문자열 합치기
            if primNum(int(num)) == True: #소수이면
                N.append(num) #N에 넣기

    N = list(set(N)) #중복제거
    
    for k in range(0, len(N)): #맨앞에0이있는경우제거
        N[k] = N[k].lstrip("0") 
    
    answer = len(list(set(N))) #중복제거후 총 개수 판단
    return answer