https://school.programmers.co.kr/learn/courses/30/lessons/42839
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
풀이
import java.util.HashSet;
class Solution {
static HashSet<Integer> set = new HashSet<>(); // 중복값 제거 위한 set
static char[] arr; // 종이조각
static boolean[] visited; // 사용여부
public int solution(String numbers) {
int answer = 0;
arr = new char[numbers.length()];
visited = new boolean[numbers.length()];
for(int i=0; i<numbers.length(); i++){
arr[i] = numbers.charAt(i);
}
recursion("",0); // 재귀함수 호출
answer = set.size();
return answer;
}
public void recursion(String str, int index){
int num;
if(str!=""){
num = Integer.parseInt(str);
if(isPrime(num)){
set.add(num); //소수이면 set에 add
}
}
if(index==arr.length){
return; // 끝까지 다했을 때
}
for(int i=0;i<arr.length;i++){
if(visited[i]){
continue; // 방문한 노드면 넘어감
}
visited[i] = true; // 방문
recursion(str+arr[i], index+1); // 방문 했을 시 재귀
visited[i] = false; // 백트래킹
}
}
// 소수 판별
public boolean isPrime(int num){
if(num==0||num==1){
return false;
}
for(int i=2; i*i<=num;i++){
if(num%i==0){
return false;
}
}
return true;
}
}재귀... 알듯 모를듯 좀 익숙해졌다. 거의 여기저기 참고해서 푼듯.
우선 재귀문을 사용하여 만들어지는 여러 문자 숫자열은 0이 맨 첫번째 자리에 들어갈경우 혹은 같은 수라 중복이 되는 값들을 제거하기위해 Hashset을 만들어 최종 값들을 저장하기로 했다. 배열 arr에는 매개변수로 받은 number문자열을 charAt메소드를 사용하여 한 자리씩 반복문으로 넣어주었다. 먼저 소수판별을 위해 만들어준 isPrime 함수를 먼저 설명해보면 0,1 은 소수가 아니므로 false를 출력하도록 하였고 for문에서 num % i 가 0일때 즉, 나머지가 0이면 약수이므로 num은 소수가 아니므로 역시 false를 출력하며 나머지경우는 소수로 판별하여 true를 리턴하도록 구현하였다 이 때 i 의 범위를 i*i 까지로 한 이유는 어떤 두 수의 최대공약수는 두 수의 곱이므로 i의 제곱근이 num과 같을때 까지만 판별을 하면 가능한 모든 경우의 범위이기 때문이다 .자 이제 문제의 재귀함수이다. 여러 영상을 살펴본 토대로 기본적으로 재귀함수의 구조를 설명해보자면 계속 본인을 반복해서 출력하는 함수인데 이러한 구조면 특정 조건에서는 반복이 멈춰야한다 예로 while문에서 특정 조건을 만족하면 while문을 나가거나 중간에 break;를 사용하여 나가듯이 재귀함수에서는 default문이 있다. 내가 만든 재귀함수에서는 if(index == arr.length){ return; // 모든 자릿수를 다 썼다면 종료 } 이 부분이 default문이다 왜냐하면 이 조건을 만족하면 더 이상 호출하지 않고 재귀문이 끝나기 때문이다. default문을 설명하기 전에 먼저 밑의 for문의 내용을 말해보면(그 뭐냐 default문에서 사용하는 재귀함수의 매개변수가 밑의 재귀문에서 계속 초기화 되므로) visited 라는 배열을 사용하였다. 이 배열은 사용 유무를 판별하여 각 문자를 사용했다가, 재귀가 끝나면 다시 사용하지 않은 상태로 돌려주는 백트래킹을 위해 사용하였다. 먼저 백트래킹을 간단히 말하면 경우의 수에 따라 예측을 해보고(트래킹: 오목 게임 할 떄 이 수를 두면 어디 막아야되고 뭐가 더 유리한지 예측하면 머릿속으로 수를 두어보는것? 를 예시로 본듯) 또 같은 상황에서 다른 경우의 수로 예측을 하기 위해 다시 그 상황으로 돌아오는 것이라고 할 수 있다. 그래서 설명하면 for문을 사용해서 이 visited배열의 i값이 true면 이미 소수 판별에 사용한 값이므로 continue로 넘어가고 그렇지 않다면 true 로 바꾸어주고 이 값을 이전 재귀함수 호출로 사용된 str과 합쳐 새로운 값을 만들어주고 판별하고 판별된 수를 만들어주기 사용한 visited[i] 는 백트래킹을위해 false로 바꾸어 준다. 이렇게 구현하면 사용한 수는 다시 사용하지 않고 재귀 함수을 호출할때마다 새로운 가능한 합쳐진는 경우의 수들을 만들고 이를 소수인지 판별해서 set에 저장하는것을 default문을 만족하기 전까지 즉, arr배열 내의 모든 값들로 경우의 수를 다 수행 할 때 까지 만들고 판별하여 저장까지 재귀 호출로 구현할 수 있었다. 마지막으로 set의 크기를 리턴하여 답을 구할 수 있었다.