프로그래머스|소수 찾기

문제설명

배열을 입력받고 그 배열안에 들어있는 숫자들을 조합해서 만들 수 있는 소수의 개수를 출력하는 문제입니다.

​

작동 순서

1. 배열을 입력받습니다.

2. 큐를 생성합니다.

3. 큐에 조합된 수와 현재 사용된 숫자들의 번호를 입력합니다.

4. 큐에서 조합된 수를 꺼내 해당 숫자를 발견 처리해줍니다.

5. 현재 사용되지 않은 숫자들을 현재 수에 조합하고 사용된 숫자도 더해서 큐에 삽입합니다.

6. 소수들을 모두 찾아줍니다.

7. 발견된 숫자들중 소수들의 개수를 구해서 출력합니다.

소스코드

from collections import deque

nums = [0 for _ in range(9876544)]
prime = [True for _ in range(9876544)]
prime[0] = False
prime[1] = False


def solution(numbers):
    answer = 0
    q = deque()
    for i in range(len(numbers)):
        q.append([numbers[i], [i]])
        while q:
            temp = q.pop()
            num = temp[0]
            nums[int(num)] = 1
            for j in range(len(numbers)):
                if j not in temp[1]:
                    q.append([int(str(num) + str(numbers[j])), temp[1]+[j]])
    for i in range(int(len(nums)**0.5)):
        n = i + i
        if prime[i]:
            while n < 9876543:
                prime[n] = False
                n += i
        if nums[i] == 1:
            if prime[i]:
                answer += 1
    return answer

후기

오랜만에 풀어보니까 너무 어렵네요.. 다른 분들은 itertools를 이용해서 많이 푸셨던데 저는 몰라서 못 썼네요... 하나하나 배워가야 할 것 같습니다.