🔑 오늘의 학습 키워드 : 완전 탐색
🔗 문제링크 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
'Coding test' 카테고리의 다른 글
99클럽 코테 스터디 17일차 TIL, 백준 / 사자와 토끼 / 17834 (0) | 2024.08.07 |
---|---|
99클럽 코테 스터디 16일차 TIL, 프로그래머스 / N-Queen (0) | 2024.08.06 |
99클럽 코테 스터디 14일차 TIL, 프로그래머스 / 징검다리 (0) | 2024.08.04 |
99클럽 코테 스터디 13일차 TIL, 프로그래머스 / 입국심사 (0) | 2024.08.03 |
99클럽 코테 스터디 12일차 TIL, 백준 / 1135 / 뉴스 전하기 (0) | 2024.08.02 |