알고리즘/programmers
42839: 소수찾기[완전탐색]
cjw.git
2021. 1. 2. 20:50
Link : programmers.co.kr/learn/courses/30/lessons/42839
1. 문제
- 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
2. 문제의 조건
- 1 <= numbers <= 7
- 0~9로 이루어져있다.
더보기
3. 문제 접근
- 시간 복잡도
문제에 완전탐색으로 분류가 주어져있습니다. 그래서 전체적으로 탐색을 진행하면 됩니다.
- 아이디어
저는 대부분 브로투포스를 대부분 재귀를 이용하여 진행합니다.
"1012034"이 주어져 있을 경우 length가 3일 때, 경우의 수는
101, 102, 100, 103, 104, 112, 110, 113, 114, 120, 123, 124, ... , 011, 012, 010, 013, 014, ... 입니다.
이 순서를 정확히 이해하셔야합니다.
이는 재귀로 구현이 비교적 쉽게 가능합니다.
즉, 이 순서마다 소수를 체크하시면 됩니다.
4. 풀이 방법
- 소수 판별 공식을 먼저 이해합니다. (밑 인용 링크)
- numbers가 비어있거나 깊이가 length 와 같다면, 다 만들어졌다는 것이므로, 소수 판별을 시작합니다.
numbers가 비어있는 경우는, numbers의 개수와 조합해야 할 length가 같을 경우, for으로 값을 넣어주는 곳이 비어있습니다. - 값을 넣어주고 만들어진 값과, 넣어야하는 값을 재귀로 보내줍니다.
- 해당 과정은 재귀에 어느정도 깊은 이해가 필요합니다.
5. 소스코드
cjw.git@gmail.com
https://53perc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0 (소수 판별 in 파이썬)