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

문제

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

프로그래머스

문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예
numbers return
"17" 3
"011" 2

입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

---

풀이

    for i in range(1, len(numbers)+1):
        nPr = itertools.permutations(numbers, i)
        ans = list(map(''.join, nPr))
        print(set(ans))

    ans_set = set(ans)

-> 맨처음에는 대강 이런식으로 계속 따로 변환 하려고 했다.

---

다른 풀이

import itertools


def isprime(n):
    if n < 2:
        return False
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True


def solution(numbers):
    answer = 0
    ans = []

    for i in range(1, len(numbers) + 1):
        ans.append(list(set(map(''.join, itertools.permutations(numbers, i)))))
    per = list(set(map(int, set(sum(ans, [])))))

    for i in per:
        if isprime(i) == True:
            answer += 1

    return answer

---

설명

1. permutation

* permutation 의 각 원소들을 하나의 리스트에 넣는 부분을 몰랐었다. 

 

permutations(iterable, r)을 사용하면 iterable의 요소들의 길이 r인 순열로 반환한다.

위의 코드에서는 모든 조합을 구하기 위해 for문을 사용하여 길이가 i로 바뀌도록 했다.

이때 line 21에서

ans.append(list(set(map(''.join, itertools.permutations(numbers, i)))))

을 print 하면 [['1', '7'], ['71', '17']]와 같은 결과가 나온다.

 

2. sum

1에서 나온 2중 리스트를 1차원으로 바꾸기 위해 sum을 사용했다.
sum은 sum(덧셈할 것, 처음에 더할 것)으로 사용할 수 있다.

처음에 더할 것을 빈 리스트 []를 넣어주면

sum(num, [])

는 [] + [1,7] + [71, 17]이 되어서 리스트끼리의 덧셈으로 [1,7, 71, 17]이 된다.

이 때 나온 조합들에서 혹시 중복이 있을 수도 있기에 set을 사용했고 이를 num이라는 빈 리스트에 넣기 위해 다시 list로 바꾸었다.

 

이렇게 구한 문자열에서 나올 수 있는 숫자들의 조합을 구하고 나면 위에서 만들어 뒀던 소수판별 함수에 숫자들의 조합 리스트를 for문으로 반복하면서 소수일 때 answer에 1을 더해 소수가 몇개인지 구하였다.

 

3. 에라토스테네스의 체: 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN) 이라고 한다. => 선형 시간에 동작할 정도로 빠르다

but, 알고리즘을 수행할 때 N의 크기만큼 리스트를 할당해야 하기 때문에 메모리가 많이 필요하다는 단점이 있다.

그래서 만약 에라토스테네스의 체를 이용해야 하는 문제의 경우 N이 1000000 이내로 주어지는 경우가 많다. 이론상 400만번 정도의 연산으로 문제를 해결할 수 있으며 메모리 또한 충분히 처리할 수 있는 크기만큼만 차지하게 된다!

 

1) 1은 제거

2) 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고 나머지 2의 배수를 모두 지움

3) 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고 나머지 3의 배수를 모두 지움.

3) 지워지지 않은 수 중 제일 작은 5을 소수로 채택하고 나머지 5의 배수를 모두 지움. (계속 반복)