소수 찾기

프로그래머스 - 소수 찾기

💪 문제 설명

해당 문제를 간단하게 설명하면 아래와 같습니다.
1. 숫자로 이루어진 문자열 numbers가 제공
2. 제공된 문자열은 길이가 1~7 사이이고, 0~9 사이의 숫자로 구성
3. 한 숫자가 하나의 쪽지로 구성되어 있다고 가정

🙏 1차 구현

저는 먼저 소수를 찾아야하므로 가장 널리 알려져있고, 가장 많이 사요하는 소수를 찾는 알고리즘인 에라토스테네스의 체 를 활용해서 소수 판별을 하기로 했습니다.

문제에서 주어진 대로 10000000 사이의 숫자의 소수를 먼저 다 구하고, 주어진 문자열의 길이 만큼 범위를 잡았습니다.

모든 순열을 구하는 것도 가능하겠지만, 저는 범위 내에 소수를 찾고, 그 소수를 리스트로 바꾸어 반대로 접근해보았습니다.

즉, 주어진 numbers에서 가능한 순열을 찾는 것이 아닌, 소수를 리스트로 변경했을 때, 그 numbers로 구성 가능한지를 따져보았습니다.

코드는 아래와 같습니다.

import math

nums = [True for _ in range(10000000)]
def solution(numbers):
    # 에라토스테네스의 체를 이용해서 소수를 구해내는 부분
    answer = 0
    nSize = len(numbers)
    temp = "9" * nSize
    temp = int(temp)
    for idx in range(2, int(math.sqrt(temp))):
        if nums[idx]:
            incre = 2
            while idx * incre <= temp:
                nums[idx*incre] = False
                incre += 1
    lstNums = list(numbers)
    # 생각을 전환해서 최대 범위 내에서 소수를 리스트로 했을 때, 해당 쪽지에 원소가 있는지를 확인
    for idx in range(2,temp):
        if nums[idx]:
            tempList = lstNums[:]
            tempIdx = list(str(idx))
            check = True
            for i in tempIdx:
                if i in tempList:
                    tempList.remove(i) # 원소를 하나씩 제거해주면서 확인
                else: # 만일 원소가 없다면 종료
                    check = False
                    break
            if check:
                answer += 1

    return answer

🦝 결과

결과는 통과 를 받을 수 있었습니다. 🤗

그러나 일부 테스트를 통과할 때, 시간이 오래 걸려 힘들게 통과한 것이 있어서 추후에 코드의 시간 복잡도를 줄이는 것을 고려해보아야겠습니다!!!