[Programmers/Java] 완전탐색 level2 : 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839#

코딩테스트 연습 - 소수 찾기

---

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 1과 011은 같은 숫자로 취급합니다.

---

문제 풀이

완전탐색 문제는 말 그대로 모든 경우의 수를 탐색하면 된다.
DFS 탐색 방법을 사용해주었다.

1. 모든 숫자 카드를 사용하여 모든 경우의 수를 보아야 한다. -> 순열이나 조합처럼 생각하면 쉽다.
2. 소수인지 아닌지, 이미 만들어진 숫자인지 아닌지를 적절히 판별해준다.
3. 이미 사용한 숫자 카드인지도 구분해주어야 한다.

해결 코드

import java.util.*; class Solution { int answer = 0; public int solution(String numbers) { char[] numberStr = numbers.toCharArray(); ArrayList<Integer> checkList = new ArrayList<Integer>(); boolean[] visit = new boolean[numberStr.length]; dfs(numberStr, 0, visit, checkList, 0); return answer; } //dfs를 이용해서 하나씩 확인해보기 public void dfs(char[] numbers, int index, boolean[] visit, ArrayList<Integer> checkList, int makeNum) { // 모든 숫자 카드를 다 사용하면 중단 if(index <= numbers.length) { for(int i = 0; i < numbers.length; i++) { if(!visit[i]) { int number = makeNum + (numbers[i] - '0'); visit[i] = true; // 방문했다고 표시 if(isPrime(number) && isCheck(number, checkList)) { checkList.add(number); answer++; } dfs(numbers, index + 1, visit, checkList, number * 10); visit[i] = false; } } } } // 소수 판별 public boolean isPrime(int n) { if(n == 0 || n == 1) return false; for (int i = 2; i<=(int)Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } // 중복 판별 public boolean isCheck(int n, ArrayList<Integer> checkList) { for(int checkNum : checkList) { if(n == checkNum) return false; } return true; } }

추가한 테스트 케이스