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

 

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

<풀이>

• 주어진 카드로 만들수 있는 경우의 수를 고려하기 위해 순열을 활용하였다.
• 순열을 직접 구현할 수도 있지만 이번에는 편하게 itertools를 활용해봤다.
• 만든 숫자에서 소수를 골라내기 위해서도 단순하게 2부터 (만든 숫자 - 1)까지를 나눠서 나머지 0이 안 되게 모든 반복문을 모두 순회하면 answer를 1 추가 시켜줬다.

from itertools import permutations
 
def solution(numbers):
    cards = [int(n) for n in numbers]
    answer = 0
    
    # visited를 만들기 위한 과정
    max_num = 0
    cards.sort()
    for c in range(len(cards)):
        max_num += cards[c] * (10 ** c)
    visited = [0 for _ in range(max_num + 1)]
    
    # 순열을 통해서 카드로 나올 수 있는 숫자를 완전 탐색
    for c in range(len(cards)):
        # itertools의 permutations를 활용하였다
        for elem in permutations(cards, c + 1):
            # card를 조합하여 숫자로 바꾸는 과정
            number = 0
            for e in range(len(elem)):
                number += elem[e] * (10 ** e)
            
            # 숫자가 0이거나 1이거나 이미 방문한 숫자면 이후 과정을 생략한다
            if number == 1 or number == 0 or visited[number]:
                continue
            visited[number] = 1
            
            # 2에서 number보다 1 작은 숫자까지 나눠서 나머지가 0이 되면 탈출하고
            for n in range(2, number):
                if not number % n:
                    break
            # 나머지가 0이 되는 숫자가 없으면 answer를 하나 추가
            else:
                answer += 1
    
    return answer