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

문제

프로그래머스 소수찾기

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

프로그래머스

 

 

코드

import itertools

def sosu(num):
    if num == 0 or num == 1:
        return False

    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def solution(n):
    answer = []
    for i in range(len(n)):
        number = set(map(int, map("".join, itertools.permutations(list(n), i + 1))))

        for num in number:
            if sosu(num):
                answer.append(num)

    return len(set(answer))

 

풀이

# 소수인지 아닌지 확인하는 함수
def check(x):
    if x == 0 or x == 1:
        return False
    for k in range(2, int(x**0.5) + 1):
        if x % k == 0:
            return False
    return True

0과 1은 소수가 아니므로 False를 반환한다.

정수론 중 

"임의의 양수 x가 합성수면 루트x(= x**0.5)보다 작거나 같은 약수를 가진다"

라는 특성을 이용하여 수인지 아닌지 확인하는 함수를 정의한다.

 

def solution(n):
    answer = []

종이조각들로 만들 수 있는 소수들을 담는 배열을 하나 생성한다.

 

for i in range(len(n)):
    number = set(map(int, map("".join, itertools.permutations(list(n), i + 1))))

• map("".join, itertools.permutations(list(n), i + 1)) 
  • i개의 종이조각을 뽑아 만들 수 있는 모든 경우의수 순열을 만들고 이를 묶어 리스트 형태로 반환한다.
  • 이때 완성된 경우의 수들은 문자열 형태이다.
• map(int, map("".join, itertools.permutations(list(n), i + 1)))
  • map함수로 경우의 수들을 정수형으로 바꾼다.
• set(map(int, map("".join, itertools.permutations(list(n), i + 1))))
  • 중복된 숫자를 고려하기 위해 집합으로 바꾼다.

 

for num in number:
    if sosu(num):
        answer.append(num)

만들어진 i자릿수 경우의 수에 대해 각각 소수인지 아닌지 판별한다.

num 만약 소수라면 answer 배열에 num을 추가한다.

 

return len(set(answer))

answer 배열에 중복된 수가 있을 수 있으니 집합으로 형태를 바꾸고

이 집합에 있는 원수의 개수(= 집합의 길이)를 반환한다.

 

 

새롭게 배운점/느낀점

• 예전보다 map 함수에 대해 이해도가 올라가니 코드를 더 간결하고 가독성 좋게 적을 수 있었다.
• 완전탐색 방법을 쓸려면 자료구조의 최적화가 중요하다고 생각했다.