🎯문제
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
✏️풀이
코드
import java.util.*;
class Solution {
Set<Integer> set;
boolean[] visit;
// 소수를 판별하는 메서드
public boolean isPrime(int n) {
for(int i = 2; i <= (int)Math.sqrt(n); i++) {
if(n % i == 0) {
return false;
}
}
return (n < 2) ? false : true;
}
// dfs 탐색 메서드
public void dfs(String numbers, String temp, int depth) {
// 만들어진 숫자의 길이가 number의 길이와 같을 경우
if(depth == numbers.length()) {
// 그 이상의 탐색을 진행하지 않고 종료
return;
}
// 탐색을 진행
for(int i = 0; i < numbers.length(); i++) {
// 방문한 적이 없을 경우
if(!visit[i]) {
visit[i] = true;
// 정수형으로 변환하여 값을 저장
set.add(Integer.parseInt(temp + numbers.charAt(i)));
// 재귀 호출
dfs(numbers, temp + numbers.charAt(i), depth + 1);
visit[i] = false;
}
}
}
public int solution(String numbers) {
int answer = 0;
visit = new boolean[numbers.length()];
set = new HashSet<>();
// 탐색을 진행
dfs(numbers, "", 0);
// 저장된 모든 값읏 소수 판별해줌
for(int num : set) {
// 소수라면 answer 증가
if(isPrime(num)) {
answer++;
}
}
return answer;
}
}설명
DFS를 통한 완전 탐색 방식으로 진행하였다.
DFS 탐색 중 반환하는 조건은 만들어진 숫자의 길이가 주어진 숫자의 길이와 동일할 경우이다. 해당 길이보다 넘어가서 탐색을 진행할 경우 이미 모든 부분을 방문했기 때문에 더이상의 숫자 추가가 불가능하기 때문이다.
탐색을 진행하면서 방문한 적이 없는 경우,
해당 위치를 방문했다는 표시를 해준다. 이후 Set에 정수형으로 변환하여 값을 저장한다. 이때 Set을 사용하는 이유는 "011", "11"은 같은 숫자로 표시를 해주기 때문이다. Set은 중복제거를 할 때 유용하며 두 문자열을 정수로 변환할 경우 모두 11이 되기 때문에 11이라는 숫자 하나만 저장이 된다.
이후 재귀호출을 통해 계속해서 탐색을 진행해가며 위의 과정을 반복한다.
모든 탐색이 끝난 뒤에 Set에는 탐색을 진행하면서 나올 수 있는 모든 숫자들이 저장이 되었을 것이다.
그렇다면 Set에 저장된 숫자들을 하나하나 꺼내서 소수 판별을 진행한다.
소수를 판별하는 메서드는 i = 2부터 진행을 한다. 소수 중 제일 작은 숫자는 2이며 에라토스테네스의 체를 이용하여 소수를 판별한다. 이때 sqrt를 사용해 제곱근까지만 반복을 진행한다. 제곱근까지 반복을 진행하는 이유는 만일 n=16일 경우, 28, 44가 나올 수 있다. 여기서 제곱근보다 큰 8은 이미 2로 나눠졌을 때 체에서 걸러지게 된다. 즉 자신의 제곱근을 넘어간다는 것은 그 전에서 걸러진 적이 없다는 뜻이므로 이후로도 걸러질 일이 없다는 뜻이다. 제곱근보다 큰 두 수를 곱해서 n이 나올 수는 없기 때문이다!
위의 메서드를 호출하면서 소수일 경우 answer의 값을 증가시켜준다. 모든 숫자의 소수판별이 끝나면 answer을 반환해서 문제를 해결할 수 있다!
💡느낀 점
소수 판별이나 DFS 모두 문제를 풀면서 많이 봤고, 익숙하게 써봤던 것들이기 때문에 해당 문제는 쉽게 풀 수 있었다. 문제의 풀이에 익숙해졌다는 것이 문제 해결능력에 얼마나 많은 도움이 되는지 알 수 있었으며, 꾸준히 하면서 실력이 느는 것이 느껴지니 조금 더 재밌게 문제를 풀 수 있는 것 같다! :)
링크
