99클럽 코테 스터디 15일차 TIL, 프로그래머스 / 소수 찾기

🔑 오늘의 학습 키워드 : 완전 탐색

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/42839

 

from collections import deque
from copy import deepcopy
import math

def solution(numbers):
    answer = 0
    
    def is_prime(n):
        if n == 0 or n == 1:
            return False
        for i in range (2, int(math.sqrt(n))+1):
            if n % i == 0:
                return False
        return True
    
    def permutation(numbers,goal_length):
        prime_cnt = 0   
        queue = deque([(str(),set())])
        while queue:
            str_num, used_index = queue.popleft()
            for idx,number in enumerate (numbers):
                if idx not in used_index:
                    tmp = str_num + number
                    tmp_idx = deepcopy(used_index)
                    tmp_idx.add(idx)
                    if len(tmp) == goal_length:
                        if int(tmp) not in made and is_prime(int(tmp)):
                            prime_cnt += 1
                            made.add(int(tmp))
                    else :
                        queue.append((tmp,tmp_idx))
        return prime_cnt
    
    made = set()
    for goal_length in range (1, len(numbers)+1):
        answer += permutation(numbers,goal_length)
    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

파이썬 itertools에 있는 permutation을 활용해서 풀어보면 되겠다

 

내장함수 이용하지 말고 풀어봐야겠다.

 

⏰ 예상 시간 복잡도 N ^2 * N!

N은 numbers 길이

1부터 N까지 만들 수 있는 조합 생성 -> N

bfs 로직하면서 소수 인지 찾기 -> N * N!

제한 사항 

numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.

 

7이어서 무난하게 통과할 수 있었던 것 같다 -> 35280

😎 알고리즘 개요

1. 소수 판별 함수 작성

 

2. 가능한 문자열 조합 만드는 함수 작성

✅ 오늘의 회고

- 내장함수를 사용하지 않고 permutation을 bfs로 구현을 했다.

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL