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

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

프로그래머스

 

문제 요약

한 자리 수가 적힌 종이 조각
종이 조각을 붙여 소수 몇 개 만들 수 있는지?

 

코드 설명

from itertools import permutations
def solution(numbers):
    num = []
    
    for n in numbers:
        num.append(n)
        
    l = len(num)
    
    count = 0
    check = set()
    
    for i in range(1, l+1):
        per = list(permutations(num, i))
    
        for p in per:
            tmp = int(''.join(p))
            # 이미 만들어진 소수면 통과
            if tmp in check:
                continue
            
            # 만들어진 소수가 아니면 추가하기
            check.add(tmp)
            if tmp == 2:
                count += 1
            
            # tmp가 소수인지 확인하는 부분
            if tmp > 2:
                cnt = 0
                for t in range(2, int(tmp**0.5) + 1):
                    if tmp % t == 0:
                        cnt += 1
                # cnt가 1이면 1로만 나누어떨어졌다는 뜻이기 때문에, 소수라는 뜻
                if cnt == 0:
                    count += 1
            
    return count

 

간단한 완전 탐색 문제이고, 순열을 활용해서 join 하는 방법도 알고 있었는데

크게 두 가지 사항 때문에 좀 헤맸다.

1. 2도 소수다

2. 시간 초과

 

오랜 만에 접한 소수 개념이라 2도 소수임을 간과하고 코드를 작성했다.

이전에 작성한 코드는 반복문을 1부터 해당 수 이전까지 돌면서 나누어서 나머지가 1인 경우가 1번만 있으면 소수로 카운팅 하는 코드였다.

이 코드가 숫자 2에도 똑같이 적용되면서 for i in range(1, 1) 이라는 실행되지 않는 반복문을 만들었다.

 

숫자 2는 따로 처리하고 2부터 돌면서 나머지가 0인 경우가 하나도 없는 경우에 소수를 카운팅 하도록 변경해서 해결했다.

 

시간 초과는 나누어서 나머지를 확인하는 과정을 해당 숫자 전까지 전체를 돌렸었는데,

소수 판별법의 특징을 생각해서 어떤 수의 제곱근까지만 확인하는 코드로 수정해 해결했다.

 

배운 점

- 2도 소수이다

- for i in range(2, 2)와 같은 반복문은 빈 리스트를 생성하므로, 아무것도 실행되지 않고 종료된다.

- 소수 판별은 해당 수의 제곱근까지만 나누어서 확인해보면, 전체를 확인할 때보다 효율적으로 확인 가능하다.