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

JunHwa Park 2020. 9. 25. 20:15

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

코딩테스트 연습 - 소수 찾기

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

programmers.co.kr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def solution(numbers):
    answer = 0
    arr = [True] * int(10 ** len((numbers)))
    size = len(arr)
    for i in range(2, size):
        if arr[i]:
            # search
            nums = [c for c in numbers]
            isPrime = True
            for k in str(i):
                flag = False
                for a in range(len(nums)):
                    if nums[a] == k:
                        flag = True
                        nums[a] = '10'
                        break
                if not flag:
                    isPrime = False
                    break
            if isPrime:
                answer += 1
            for j in range(i * 2, size, i):
                arr[j] = False
    return answer

cs

 

완전탐색이다.

에라토스테네스의 체 방식으로 소수를 찾고, 소수라면 주어진 수로 만들 수 있는지 확인하면 된다.