[알고리즘] 프로그래머스 - 소수 찾기 - 42839 파이썬 문제 풀이

문제 링크

문제

입출력 예시

조건

조건을 보면 숫자가 최대 7개까지만 있기 때문에 부분집합, 순열로 다 구해서 탐색하더라도 시간복잡도가 충분하다. 즉, 완탐 문제이다.

풀이

from itertools import permutations
from itertools import combinations
from collections import defaultdict

def solution(numbers):
    arr = list(numbers)
    all_list = defaultdict(list)
    table = {}
    ans = []
    
    for i in range(1, len(arr)+1):
        for j in combinations(arr, i):
            all_list[j] = 0
    
    for i in all_list:
        for j in permutations(i, len(i)):
            table[int(''.join(j))] = 0
    
    for i in table:
        check = True
        if i == 0 or i == 1:
            check = False
        for j in range(2, i):
            if i % j == 0:
                check = False
                break
        if check: ans.append(i)

    return len(ans)

파이썬을 사용한지 얼마 되지 않았다보니... 순열과 조합이 내장함수가 있는지 처음 알게 되었다... 직접 구현해서 풀었는데 다른 사람 풀이를 보니 내장함수가 있어서 허탈했다...ㅎ 그래도 지금이라도 알아서 참 다행이라는 생각이 들었다.
아이디어는 원소가 들어있는 부분집합을 모두 구하고 각 부분집합마다 모든 순열 조합을 구해서 그 숫자들 중 소수인 숫자를 찾아내는 방법을 사용했다.
부분집합과 순열을 구하다보면 중복된 값이 발생하기 때문에 dictionary를 활용해서 중복된 것들을 제거함으로써 시간복잡도를 조금이라도 줄이려고 했다.