프로그래머스 알고리즘 문제풀이: 소수찾기

 

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

풀이

• 완전 탐색 문제
• 주어진 numbers 문자열의 순서를 바꿔 배치한 후 만들어낼 수 있는 숫자들 중 소수의 개수를 구하는 문제.
  • 즉, 순열 + 소수 검사를 요구하는 문제.
• python의 경우 itertools의 permutations를 사용하여 순열을 생성하고 약수가 존재하면 False, 없다면 True를 반환하는 소수검사 함수를 생성하여 체크했다.
• 단, 그대로 제출할 시 시간초과에 걸릴 수 있다.
  • numbers는 길이가 1이상 7 이하이고 숫자는 0~9 이기 때문에 최악의 경우 9999999를 체크해야 한다.
• 효율화를 위해 소수 체크 함수를 효율화시켰다.
  • a * b = N의 경우 a와 b는 N의 약수이다.
  • min(a, b)<=sqrt(N), max(a, b)>=sqrt(N)이기 때문에 N의 약수 존재 여부는 2부터 square root N까지만 검사하면 된다.

예시 코드

Javascript

function solution(numbers) {
    const check = (n) => {
        if (n<2) return false 
        for (let i=2; i < Math.floor(Math.sqrt(n))+1; i++){
            if (n%i===0) return false 
        }
        return true
    }
    
    const permutator = (inputArr) => {
      let result = new Set()
      const arr = (inputArr) => {
          let temp = [];
          for (const i of inputArr){
              temp.push(i)
          }
          return temp
      }    
      
      const permute = (arr, m = '') => {
        if (arr.length === 0) {
          result.add(Number(m))
        } else {
          for (let i = 0; i < arr.length; i++) {
            let curr = arr.slice();
            let next = curr.splice(i, 1);
            permute(curr.slice(), m+next)
            permute(curr.slice(), m)
         }
       }
     }
     permute(arr(inputArr))
     return result;
    }
    
    return Array.from(permutator(numbers)).filter((i)=>check(i)).length
}

Python

• itertools 라이브러리 사용

from itertools import permutations
import math 
def check_sosu(n):
    if n == 1 or n==0:
        return False
    for i in range(2, int(math.floor(math.sqrt(n)))+1): # math.sqrt(n) 이후 float의 소수점 아랫부분을 버림했다. 
        if n%i==0:
            return False
    return True 

def solution(numbers):
    answer = 0
    ans_set = set()
    for i in range(1,len(numbers)+1):
        for x in set([int(''.join(x)) for x in permutations(numbers,i)]):
            if check_sosu(x):
                ans_set.add(x)  
    answer = len(ans_set)
    return answer

• permutation 생성 함수 작성 

def solution(numbers):
    answer = 0
    N = len(numbers)
    nums = set()
    def check_sosu(n):
        if n < 2:return False 
        for i in range(2,int(math.floor(math.sqrt(n)))+1):
            if not n%i:
                return False 
        else:return True 
    
            
    visit = [0]*(N+1)
    def perm(k,num):
        if k == N and num:
            if int(num) > 1:
                nums.add(int(num))
            return 
        else:
            for i in range(N):
                if visit[i]:
                    continue
                visit[i] = 1 
                perm(k+1,num+numbers[i])
                perm(k+1,num)
                visit[i] = 0
                
    perm(0,'')
    for n in nums:
        if check_sosu(n):
            answer += 1
    return answer