[프로그래머스]소수 찾기 - 완전탐색

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

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

 

from itertools import permutations
import math

def solution(numbers):
    case = []
    answer = 0
    
    for i in range(len(numbers)):
        permu = list(map(''.join, permutations(numbers, i+1)))
        for j in permu:
            case.append(int(j))
            
    case = list(set(case))

    for j in case:
        flag = True
        # 2보다 작은수는 건너뜀
        if j < 2:
            continue
            
        # 2부터 제곱근+1(제곱근 수도 포함하려고 +1 range 에서) 까지 반복하면서 나누어봄, 나눠지면 소수 X
        for x in range(2, int(math.sqrt(j))+1): 
            if j % x == 0: # 소수가 아님
                # 해당 숫자는 소수가 아니라는 flag
                flag = False 
                break
        # 소수가 맞을시에만 count++
        if flag:
            answer += 1
    
    return answer

 

문제 해결 Point

해당 문제의 핵심은 두 가지로 나누어진다. 첫번째는 주어진 numbers 조합에서 순열을 만들어 내는 것이고, 두번째는 만들어진 순열에서 소수를 찾는 과정이다.

 

순열을 만드는 것은 파이썬의 itertools.permutations를 이용하면 편리하게 만들 수 있다.

소수를 판별하는 방법은 2부터 구하려는 수의 제곱근까지 반복문을 순회하면서 나누어 지는 수가 있는지를 확인한다. 이 때 나누어지는 수가 있다면 소수가 아니다.

 

그럼 위의 코드를 순서대로 풀어 설명해보겠다.

1. 먼저 numbers 리스트를 순회하면서 각 자릿수(한자리수, 두자리수..) 별로 순열을 만들어 case 리스트에 값을 넣어둔다.
   [1, 17, 71]과 같은 값이 들어가게됨
2. 중복으로 생성된 수를 제거하기 위해 set -> list 함수를 이용한다.
3. 본격적으로 소수를 찾기 위해 case 리스트를 순회한다.
   
   1. 소수임을 체크하기 위한 flag 변수를 설정해둔다.
   2. 만약 2보다 작은 수라면 건너 뛴다.
   3. 2부터 해당하는 수의 제곱근 까지 반복문을 진행한다.
      1. 여기서 나누어 진다면 소수가 아니라는 flag = False를 설정하고 반복문을 빠져나온다.
   4. 소수가 맞다면 answer 카운트를 1 증가시켜 준다.

 

소수를 판별하는 알고리즘에는 여러 가지 방법이 존재하는데 항상 잘 기억이 나지 않아 은근히 애를 먹었던 문제였다. 이번기회에 확실하게 이론을 집고 넘어가게 된 것 같다.