[스파르타] 99클럽 2기 코테스터디 10일차 TIL / 소수 찾기

프로그래머스: 소수 찾기 (링크)

소수 찾기

 

얼마 전 99클럽 1기에서 풀었던 문제라 이번에는 다른 분들의 풀이를 참고해서 다시 풀어봤다. 풀이 (1)는 set을 미리 정의해 두고 permutations으로 모든 조합을 넣은 후 다시 소수 판별을 하는 방식이었다. 풀이 (2)는 코드가 엄청 깔끔해 보여서 가져왔는데 makeCombinations 함수에서 재귀로 모든 경우의 수를 돌리는 게 신기했다. 만약 numbers에 '123'이 들어오게 되면 makeCombinations의 str1, str2에는 각각 ('', 123), (1, 23), (123, '') -> (13, 2), (132, '') -> (12, 3), (123, '') 이런 식으로 가능한 모든 조합이 생성된다. 이런 방법은 생각 못했는데 잘 기억해 뒀다가 나중에 써봐야겠다.

 

## 풀이 (1)
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)
    
    
 ## 풀이 (2)
primeSet = set()

def isPrime(number):
    if number in (0, 1):
        return False
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))
    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])

def solution(numbers):
    makeCombinations("", numbers)
    answer = len(primeSet)
    return answer

오늘 미들러 풀이 끝!