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

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42839

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

 

소수 찾는 문제는 굉장히 전통적인 문제라서 효율적으로 찾는 방법을 알아두면 편하다.

(아마 LV1에 소수 찾는 문제 중 효율정 테스트가 빡센 문제가 있는걸로 안다)

 

풀이

 

def isPrime(num):
    import math
    
    if num == 2:
        return True
    
    if num == 1 or num % 2 == 0:
        return False
    else:
        for divide in range(3, int(math.sqrt(num) + 1), 2):
            if num % divide == 0:
                return False
            
    return True

def solution(numbers):
    from itertools import permutations

    num_per = []
    
    for len_ in range(len(numbers)):
        num_per += list(permutations(numbers, len_+1))
        
    num_set = set({})
        
    for num_string in num_per:
        num_set.add(int(''.join(num_string)))
        
    answer = 0
    
    for num in num_set:
        if isPrime(num):
            answer += 1
        
    return answer

 

로직은 다음과 같다.

 

1. 순열을 이용해서 글자 단위로 길이가 1부터 최대 문자열 길이까지 순열 생성

2. 생성한 순열을 join 함수로 합쳐서 집합 자료형에 넣는다.(중복 제거)

3. 집합에서 문자를 하나씩 꺼내서 소수인지 검사하여 소수이면 answer+1

---

 

시간 복잡도

 

permutations 함수부터가 O(N!)으로 압도적으로 높.......다.......

글자의 길이가 1부터 7로 제한되어서 통과한 듯.

 

 

다른 사람의 풀이를 보면서 알게 된 점

 

에라토스테네스의 체

 

풀이를 보는데 에라토스테네스의 체라는게 나오길래 뭐지???했었다.

찾아보니 고대 그리스의 수학자 에라토스테네스가 만든 소수를 찾는 방법이라고 한다.

체에 수를 걸러내 듯이 소수를 찾는다고 해서 에라토스테네스의 체라고 한다는데 

1부터 n 사이에 있는 수들에 대해서 2, 3, 5, 7, ...과 같은 수의 배수들을 제외하면 남은 것이 소수가 된다는 원리이다.

 

|= 연산자

 

a |= b

 

+=나 -=와 같은 연산자는 많이 사용했는데 |=와 같은 연산자는 처음 봐서 뭐지 했었다.(비트 연산자 아닌가?)
|는 비트 or 연산자이니 당연하게도 a |= b라고 작성하면 a와 b를 or 연산한다는 연산자이다.

그런데 이게 set 자료형에서도 사용이 가능하다.

밑에 작성할 풀이에서는 이 연산자를 set 자료형과 함께 사용하는데 이 경우 합집합 연산을 하게된다.

 

** 연산자

 

25 ** 0.5 #5.0
2 ** 3    #8.0

 

이런 형태의 연산자가 있는 건 알았는데 실제로 사용해보진 않아서 정리한다.

**는 n제곱 연산자이다. a ** b와 같은 형태로 a의 b제곱이라는 연산을 해준다.

재밌는 점은 b 부분에 1보다 작은 수를 넣으면 루트 연산을 해준다.

위의 25 ** 0.5에서 결과값이 5.0으로 math.sqrt(25)와 같은 값임을 알 수 있다.

 

map 함수의 충격적인 사용 : 앞에 함수

 

n = map(''.join, permutations(numbers, len_+1))

 

map 함수가 성분을 하나씩 꺼내서 처리하는 함수라는 것은 알고 있었는데

앞에 함수를 넣어서 사용이 가능할 줄은 몰랐다.

 

permutations의 결과값으로 tuple들이 나오게 되는데

이 tuple들을 하나씩 꺼내서 ''.join 연산을 해준다.

이 때, 원래는 (사이값).join(입력값)으로 사용하나 join 뒤의 ()가 사라진 모습을 보인다.

예를 들어,

 

('1', '7', ), ('2', '7', )

 

이 있다면,

 

('1', '7', )을 꺼내서 '17'로 만들고, ('2', '7', )을 꺼내서 '27'을 만든다.

 

위를 이용한 풀이

 

def solution(numbers):
    from itertools import permutations
    
    num_per = set()
    
    #모든 조합 set에 넣어줌
    for len_ in range(len(numbers)):
        num_per |= set(map(int, map(''.join, permutations(numbers, len_+1))))
        
    #0, 1 제거
    num_per -= set(range(0, 2))
    
    #num_per가 빈 리스트인 경우 max 함수 error 처리
    try:
        #2부터 num_per의 최댓값이 루트 취한 값 + 1 사이에서 증가시켜 가면서 배수 제외
        for num in range(2, int(max(num_per) ** 0.5) + 1):
            num_per -= set(range(num * 2, max(num_per) + 1, num))
    except ValueError:
        return 0

    return len(num_per)

 

로직은 다음과 같다.

 

1. 순열을 이용해서 글자 단위로 길이가 1부터 최대 문자열 길이까지 순열 생성해서 집합 자료형에 넣어준다.

2. 2부터 sqrt(n)까지 수들에 대해 1부터 n사이의 정수에 대해 배수를 구해준 후

   1에서 구한 집합에서 빼준다.

3. 남은게 소수의 집합

 

 

고찰

 

여러가지 풀이를 많이 알게 되는 문제였다.

문제 자체를 푸는데 어려움은 없었다.