99클럽 코테 스터디 5일차 TIL + 프로그래머스 소수 찾기

 

문제 설명

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

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

 

제한사항

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

 

예시

"17" 

[1, 7, 17, 71] -> 여기서 소수는 7, 17, 71 로 정답은 3

 

아마도 이 문제는 파이썬의 itertools를 쓸 수 있다는걸 확인하는 순간 문제푸는 시간이 줄음과 동시에 파이썬 최고를 외칠 것✨
itertools.permutation의 경우 O(N!)으로 11개의 입력까지 수용이 가능한데,,,
마침!!! 이 문제는 7자리 숫자가 최대라는 점에서 사용이 가능하다는 것을 눈치챌 수 있었다!

 

문제 풀이 순서

1. 먼저 문자열을 쪼개서 나열될 수 있는 모든 순열(문자열의 순서 고려 17, 71)을 구한다

• 이때 1자리 숫자는 2이상부터 시작이 가능하다는 조건을 추가해주기 메모...📝

2. 소수의 갯수 세기

• 소수 : 1과 자기 자신으로만 나누어지는 숫자
• 다른 수로 나누다가 나머지가 0이 되는 순간 바로 isFlag = false로 두고 소수에서 탈락이다.

 

코드로 구현하기

from itertools import permutations

def solution(numbers):

    size = len(numbers)
    num = ''
    candidate = []
    cnt = 0
    isFlag = True
    
    # 문자열 길이 1씩 자르기
    numbers = list(map(str,numbers))
    
    # 1개짜리 순열부터 문자열 길이의 순열까지 생성
    for i in range(1,size+1):
        for j in permutations(numbers, i):
            num = int(''.join(j))
            
            # 만약에 candidate에 포함되어있지 않고, 2보다 큰 수라면 후보군으로 넣어준다.
            if num not in candidate and num >= 2:
                candidate.append(num)
    
    for i in candidate:
    	
        # 2부터 시작해서 자기자신 전까지의 수로 나누다가 한번이라도 나누어 떨어지면 소수에서 탈락! 
        for j in range(2,i):
        	# 이전 계산에서 False가 되었더라도 break 걸리기 전까지는 계속 True 유지해주기
        	isFlag = True
            if i % j == 0:
                isFlag = False
                break
            
        if isFlag == True:
            cnt += 1
        
    
    answer = cnt
    return answer

 

 

결과

 

결과는 성공!!

 

다만 최대로 걸리는 시간이 2422.40ms로 꽤나 오래걸리는 코드이긴 하다...

소수의 갯수 구하는 알고리즘에서 좀 더 단축시키고자 '에라토스테네스의 체'를 이용한다면 좀 더 빨라지려나..?