문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
풀이 방법 생각
숫자로 조합할 수 있는 모든 경우의 수에 대해 소수인지 확인해야 가능하다고 생각했다. 중복은 set을 이용해서 제거하고 모든 경우의 수를 만들기 위해 순열을 사용하려고 했지만 재귀적으로 접근할 방법이 잘 떠오르지 않아 뱀귤님의 블로그를 참고했다.
참고 : 뱀귤 블로그 https://bcp0109.tistory.com/14
내 코드
import java.util.HashSet;
import java.util.Iterator;
class Solution {
public int solution(String numbers) {
int answer = 0;
int[] arr = new int[numbers.length()];
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < numbers.length(); i++) {
arr[i] = numbers.charAt(i) - '0';
}
for (int i = 1; i <= numbers.length(); i++) {
per(set, arr, 0, numbers.length(), i);
}
Iterator<Integer> it = set.iterator();
while(it.hasNext()){
if(find(it.next()))
answer++;
}
return answer;
}
public void per(HashSet<Integer> set, int[] arr, int depth, int n, int r) {
if(depth == r){
String num = "";
for (int i = 0; i < r; i++){
num += String.valueOf(arr[i]);
}
set.add(Integer.parseInt(num));
return;
}
for (int i = depth; i < n; i++) {
swap(arr, depth, i);
per(set, arr, depth + 1, n, r);
swap(arr, depth, i);
}
}
void swap(int[] arr, int depth, int i) {
int temp = arr[depth];
arr[depth] = arr[i];
arr[i] = temp;
}
public boolean find(int x) {
if (x == 1 || x == 0)
return false;
for (int i = 2; i < x; i++) {
if (x % i == 0)
return false;
}
return true;
}
}
다른 사람 풀이
import java.util.HashSet;
class Solution {
public int solution(String numbers) {
HashSet<Integer> set = new HashSet<>();
permutation("", numbers, set);
int count = 0;
while(set.iterator().hasNext()){
int a = set.iterator().next();
set.remove(a);
if(a==2) count++;
if(a%2!=0 && isPrime(a)){
count++;
}
}
return count;
}
public boolean isPrime(int n){
if(n==0 || n==1) return false;
for(int i=3; i<=(int)Math.sqrt(n); i+=2){
if(n%i==0) return false;
}
return true;
}
public void permutation(String prefix, String str, HashSet<Integer> set) {
int n = str.length();
//if (n == 0) System.out.println(prefix);
if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
}
}
소수를 확인하는 함수도 모든 짝수는 거르고 제곱근까지 이용해서 필요한 수까지만 사용했다. 순열루틴은 swap해서 원하는 부분으로 가져오는 것이 아닌 substring을 이용해서 원하는 부분을 가져오는 함수로 나타냈다.
알고리즘을 한가지로 구현하는 것이 아닌 다양한 방법으로 생각해보고 실제로 구현해서 올바르게 작동하는지 알아봐야겠다.
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
타겟 넘버 (0) | 2021.07.14 |
---|---|
카펫 (0) | 2021.07.13 |
모의고사 (0) | 2021.07.12 |
H-Index (0) | 2021.07.12 |
가장 큰 수 (0) | 2021.07.12 |