42839: 소수찾기[완전탐색]

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.tistory.com/84

 

---

 

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 파이썬)