🕵️‍♀️ 소수 찾기

프로그래머스 소수 찾기 level2 풀이과정과 고민 ( 정답 코드 없음 )

소수 찾기

풀이 과정

• 문제를 보자마자 생각한 건 경우의 수 였다.
  다행히 배열의 최대 길이는 7이었고 대충 계산해보니 최대 12800개정도의 경우의 수가 나왔다.
  근데 가만 생각을 해보니 12800개의 숫자를 하나식 소수를 판단해야하니 시간 복잡도가 너무 커질 것 같았다.

소수를 판단하는 가장 빠른 로직

• 소수를 판단하려면 단순 무식하게 2부터 판단하려는 숫자n-1 까지 반복문을 돌면서 n을 나누어서 소수인지 판단을 한다.

  • 이렇게 되면 7자리 숫자는 1개 판단하는데 최소 백만번을 넘게 판단해야하니 절대 절대 쓸 수 없는 알고리즘이다.

• 어떻게 하면 더 시간을 줄일 수 있을까 고민하다가 든 생각이 판달할 숫자의 절반을 넘은 수는 절대 약수가 될 수 없다는게 생각이 났다.
  그래서 반복문의 횟수를 반을 줄일 수 있다.
  하지만 역시나 아직은 부족하다.

• 이전에 자료구조공부할 때 소수 구하는 알고리즘을 배운게 생각이나서 책을 살펴봤는데 나누려는 숫자의 제곱근 밑으로 나눈다는 개념을 알게 됐다.
  제곱은 밑으로만 나누면 소수인지 판단을 할 수 있다는 걸 알게 됐고
  파이썬에서 제곱근을 구하는 모듈을 검색해서 알게 됐다.
  시간복잡도는 O(√n)이 된다.

import math 

math.sqrt()

sqrt()를 활용해서 제곱근을 구할 수 있게 됐다.

• 그리고 소수를 판별하는 함수를 만들었다.

def sosu(n):
    if n < 2: 
        return False

    num = int(math.sqrt(n)) + 1
    for i in range(2, num):
        if n % i == 0: 
            return False
    return True

순열을 만드는법

• 효율좋은 소수판별기 함수를 만들었는데 문제가 생겼다.
  문자열로 입력을 받은 숫자들을 1자리 2자리 3자리 수로 모든 경우의 수를 구현하는법이 떠오르지 않았다.
  벌써 문제를 푸는 시간이 3시간이 지나가게 되고 지쳐서 풀이법을 보게 됐다.

permutations

• 순열을 만들어내는 함수 permutations를 알게 됐다.
  아 이런 강력한 기능을 내장하다니 하면서 수학에 대한 이해의 부족이 마음이 아팠다.

permutations(number, i) 함수는 인자에 순열로 만들 숫자와 자리수(i)를 넘겨주면 이터레이블 객체로 반환하고 반복문 돌려서 꺼내보면 튜플로 나온다. 튜플의 각 숫자는 문자열로 반환되기 때문에 int함수를 써야한다.

결국

• 방법만 알았으면 나머지를 풀었어야 하는데 너무 지쳐서 풀이 과정까지 보고 풀었다.

• set함수를 사용해서 반환된 값을 리스트로 만들어서 013 과 13같은 숫자를 동일하게 처리했다.

• 비록 또 못풀었지만 다양한 방법을 알아간다 생각하고 포기하지말고 열심히 하자!

• 코드는 깃헙 참조